#include <fstream>

using namespace std;
ifstream f("djikstra.in");
ofstream g("djikstra.out");
int A[25000][25000],a,max1,b,c,inainte[25000],s,i,N,viz[25000],j,v;
long long M,C[25000];
int main()
{f>>N>>M;
 for(i=1;i<=M;i++) {f>>a>>b>>c;
                    A[a][b]=c;
                }
 s=1;
 viz[s]=1;max1=0;
 for(i=1;i<=N;i++) {C[i]=A[s][i];if(C[i]>max1) max1=C[i];
                    inainte[i]=s;}
 C[0]=max1+1;
 //g<<C[0]<<'\n';
 //for(i=1;i<=N;i++) g<<C[i]<<' ';
 inainte[s]=0;
 for(i=1;i<=N-2;i++)
 { v=0;
 for(j=1;j<=N;j++)
    if(viz[j]==0&&C[j]!=0&&C[j]<C[v]) v=j;
 if(v!=0)
 { viz[v]=1;
   for(j=1;j<=N;j++)
    if(A[v][j]!=0&&viz[j]==0&&(C[j]==0||C[v]+A[v][j]<C[j]))
   {C[j]=C[v]+A[v][j];
    inainte[j]=v;
   }
 }

   }

 for(i=2;i<=N;i++) g<<C[i]<<' ';
 g<<'\n';




    return 0;
}