#import<fstream.h>
#define F(n,z)for(i=z;i<=n;++i)
int a[250001][4],d[50001],n,m,i,j,k,o=1,c,p;ifstream f("dijkstra.in");ofstream g("dijkstra.out");main(){f>>n>>m;F(1,n)d[i]=2e6;F(1,m){f>>a[i][1]>>a[i][2]>>a[i][3];if(a[i][1]==1)d[a[i][2]]=a[i][3];}while(o&&(o=0),++p<n)F(1,m){k=a[i][1];j=a[i][2];c=a[i][3];if(d[j]>d[k]+c){d[j]=d[k]+c;o=1;}}F(2,n)g<<(d[i]<2e6?d[i]:0)<<" ";}