#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);
         j=0;a=b=c=0;
         while (cgh[j]!=32){
               a*=10;
               a+=(cgh[j]-'0');
               ++j;
               }
         ++j;
         while (cgh[j]!=32){
               b*=10;
               b+=(cgh[j]-'0');
               ++j;
               }
         ++j;
         while (cgh[j]){
               c*=10;
               c+=(cgh[j]-'0');
               ++j;
               }               
         //scanf("%d %d %d",&a,&b,&c);     
         veci[a].pb(b);     
         cost[a].pb(c);     
         }     
     //---------------------------     
     bitset <NMAX> iq;     
     queue<int> 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;     
 }