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