#include<fstream>
using namespace std;
ifstream in("dijkstra.in");
ofstream out("dijkstra.out");
int a[10000][10000],d[10000],viz[10000],n,m,i,j,k,cost,indmin,mini;
int main(){
in>>n>>m;
for(i=1;i<=n;i++)
    d[i]=2147483627;
d[1]=0;
for(k=1;k<=m;k++){
    in>>i>>j>>cost;
    a[i][j]=cost;
}
for(k=1;k<=n;k++){
    mini=2147483627;
    for(i=1;i<=n;i++){
        if(viz[i]==0){
            if(d[i]<mini){
                mini=d[i];
                indmin=i;
            }
        }
    }
    viz[indmin]=1;
    for(j=1;j<=n;j++)
        if(a[indmin][j]!=0)
            if(d[indmin]+a[indmin][j]<d[j])
                d[j]=d[indmin]+a[indmin][j];
}
for(i=2;i<=n;i++)
    if(d[i]==2147483627)
        out<<0<<" ";
    else
        out<<d[i]<<" ";
return 0;
}