#include<iostream.h>
#include<fstream.h>
int i,j,k,n,m,a[250001][4],c[50001],ok=0;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
int main()
{f>>n>>m;
for(i=2;i<=n;i++)
        c[i]=1001;
for(i=1;i<=m;i++)
        {f>>a[i][1]>>a[i][2]>>a[i][3];
          if(a[i][1]==1) c[a[i][2]]=a[i][3];}
 
c[1]=0;
 ok=1; int nr=1;
while(ok==0 && nr<n)
{  ok=1;
for(k=1;k<=m;k++)
         if(c[a[k][2]] > c[a[k][1]] + a[k][3])
                                 {c[a[k][2]]=c[a[k][1]]+a[k][3];
                                  ok=0;}
nr++;}
for(i=2;i<=n;i++)
     if(c[i]==1001)  h<<"0 ";
                else  g<<c[i]<<" ";
return 0;
}