#include <stdio.h>     
#include <algorithm>     
#include <queue>     
#include <vector>     
#include <bitset>     
using namespace std;     
#define NMAX 65536     
#define INF 0x3f3f3f3f     
#define pb(a) push_back(a)     
vector<int> veci[NMAX],cost[NMAX];
char cgh[32];     
int n,m,a,b,c,i,d[NMAX],nod,j;      
int main()     
 {     
     freopen ("dijkstra.in","r",stdin);     
     freopen ("dijkstra.out","w",stdout);     
     scanf("%d %d\n",&n,&m);     
     for (i=1;i<m+1;++i){     
         gets(cgh);
         sscanf(cgh,"%d %d %d",&a,&b,&c);
         //scanf("%ld %ld %ld",&a,&b,&c);     
         veci[a].pb(b);     
         cost[a].pb(c);     
         }     
     //---------------------------     
     bitset <NMAX> iq;     
     queue<long> q;     
     memset(d, INF, sizeof(d));     
          
     d[1]=0;     
     q.push(1);     
     iq[1]=1;     
          
     while (!q.empty()){     
           nod=q.front();     
           q.pop();     
           iq[nod]=0;     
           for (i=0;i<veci[nod].size();++i)     
               if (d[nod]+cost[nod][i]<d[veci[nod][i]]){     
                  d[veci[nod][i]]= d[nod] +cost[nod][i];     
                  if (!iq[veci[nod][i]]){     
                     q.push(veci[nod][i]);     
                     iq[veci[nod][i]]=1;     
                     }     
                  }     
           }     
     //-----------------------------------     
     for (i=2;i<n+1;++i)     
         if (d[i]<INF)printf("%d ",d[i]);  
         else printf("0 ");  
       
     return 0;     
 }