#include<bits/stdc++.h>
using namespace std;
const int SIZE = 100;

vector < pair < int , int > > v [SIZE];  
int dist [SIZE];
bool vis [SIZE];
int V,E;

void dijkstra(){
    
    // set the vertices distances as infinity
    for(int i=0;i< SIZE; i++)
        dist[i]=1e9;
        
    // set all vertex as unvisited
    memset(vis, false , sizeof vis);    
    
    // source distance to itself equals to 0
    dist[1] = 0;
    
    // priority_queue to do the job
    priority_queue < pair < int , int >,vector<pair<int,int>>,greater<pair<int,int>> > pq; 
    
    // insert the source node with distance 0
    pq.push({0 , 1});                         

    while(!pq.empty()){

        pair <int , int> p = pq.top();        // pop the vertex with the minimum          distance
        pq.pop();

        int x = p.second;                       // x is the current vertex
        
        if( vis[x] )                            // check if the popped vertex is
            continue;                           // visited before
                                 
        vis[x] = true;                           

        for(int i = 0; i < v[x].size(); i++){
            int e = v[x][i].first; int w = v[x][i].second;
            if(dist[x] + w < dist[e]  ){            // check if the next vertex             distance could be minimized
                dist[e] = dist[x] + w;
                pq.push({dist[e],  e} );           // insert the next vertex               with the updated distance
            }
        }
    }
    for(int i=1;i<=V;i++)
        cout<<dist[i]<<" ";
}

int main(){
    
    cin>>V>>E;
    for(int i=0;i<E;i++){
        int x,y,weight ;
        cin>>x>>y>>weight ;
        v[x].push_back({y,weight}) ;
    }
    dijkstra();
    
    return 0;
}