#include <fstream>
#include <iostream>
#include <vector>
#include <map>
#include <queue>
 
const int MAX = 2001;
 
using namespace std;
 
template <class T> struct greater2 : binary_function <T, T, bool> {
    bool operator() (const T& x, const T& y) const {
        return x.second > y.second;
    }
};
 
 
int main(){
    ifstream f("dijkstra.in");
    ofstream g("dijkstra.out");
    int n, m, i;
    f>>n>>m;
    map<int, vector< pair<int, int> > > outbound;
    map<int, int> distances;
    map<int, bool> visited;
     
    for (i = 1; i <= n; i++){
        distances[i] = MAX;
        visited[i] = false;
    }
     
    for (i = 0; i < m; i++){
        int a, b, c;
        f>>a>>b>>c;
        outbound[a].push_back(make_pair(b, c)); 
    }
    f.close();
     
     
    priority_queue< pair<int, int>, vector< pair<int, int> >, greater2< pair<int, int> >  > qu;
    qu.push( make_pair(1, 0) );
    distances[1] = 0;
     
    pair <int, int> c;
     
    while (! qu.empty() ){
        c = qu.top();
        //cout<<"Expanding "<<c.first<<endl;
        qu.pop();       
        visited[ c.first ] = true;
         
        vector< pair<int, int> > v = outbound[c.first];
        for ( vector< pair<int, int> >::iterator it = v.begin(); it != v.end(); ++it){
            pair<int, int> p = *it;
            if (visited[p.first]) continue;
            if ( c.second + p.second < distances[p.first] ){
                distances[p.first] = c.second + p.second;
                qu.push( make_pair(p.first, distances[p.first] ) ); 
            }
        }
        /*
        for (i = 2; i <= n; i++){
                cout<<i<<":"<<distances[i]<<" ";
        }
        cout<<endl;
        */
    }
     
     
    //return 0;
    for (i = 2; i <= n; i++)
        if (distances[i] == MAX ) g<<"0 ";
        else g<<distances[i]<<" ";
    g.close();
     
    return 0;
}