#include <cstdio>  
#include <cstring>  
 #include <set>  
 #include <vector>  
 using namespace std;  
   
 #define pb push_back  
 #define mp make_pair  
 #define MAXN 50100  
 #define INF 1000000000  
   
 int N, M, d[MAXN]; vector<int> G[MAXN], C[MAXN];  
 set< pair<int, int> > T;  
   
 void solve(void)  
 {  
     int i, j, k, val, x;  
       
     for(i = 2; i <= N; i++) d[i] = INF;  
     T.insert( mp(0, 1) );  
   
     while( T.size() > 0 )  
    {  
         val = (*T.begin()).first, x = (*T.begin()).second;  
         T.erase(*T.begin());  
         for(i = 0; i < G[x].size(); i++)  
          if(d[ G[x][i] ] > val + C[x][i] )  
             d[ G[x][i] ] = val + C[x][i], T.insert(mp(d[G[x][i]],G[x][i]));  
     }  
 }  
   
 int main(void)  
 {  
     freopen("dijkstra.in", "rt", stdin);  
     freopen("dijkstra.out", "wt", stdout);  
   
     int i, a, b, c;  
   
     scanf("%d %d\n", &N, &M);  
     for(i = 1; i <= M; i++)  
         scanf("%d %d %d\n", &a, &b, &c), G[a].pb(b), C[a].pb(c);  
   
     solve();  
   
     for(i = 2; i <= N; i++)  
         printf("%d ", d[i] == INF ? 0 : d[i]);  
   
     return 0;  
 }