#include <fstream>

using namespace std;
ifstream fin ("dijkstra.in");
ofstream fout ("dijkstra.out");
int n,m,D[50001],T[50001],S[50001],a[20000][20000],R,x,y,z;
void init()
{
    S[R]=1;D[R]=0;T[R]=0;
    for(int i=1;i<=n;i++)
        if(i==R) D[i]=0;
    else if(a[R][i]<10001) {T[i]=R;D[i]=a[R][i];}
    else {D[i]=10001;T[i]=0;}
}
int cautak()
{
    int mn=99999,mni=0;
    for(int i=1;i<=n;i++)
    if(!S[i]) if(S[i]<mn) {mn=S[i];mni=i;}
    return mni;
}
int nodk(int k)
{
    S[k]=1;
    for(int i=1;i<=n;i++)
        if(!S[i])
        if(D[i]>D[k]+a[k][i]) {D[i]=D[k]+a[k][i];T[i]=k;}
}
int main()
{
    fin>>n>>m;
    for(int i=1;i<=m;i++) {fin>>x>>y>>z;a[x][y]=z;}
    for(int i=1;i<=n;i++)
    for(int j=1;j<=n;j++) if(!a[i][j]) a[i][j]=10001;
    R=1;
    init();
    while(cautak()) nodk(cautak());
    for(int i=2;i<=n;i++) if(D[i]>1000) fout<<'0'<<' '; else fout<<D[i]<<' ';
    return 0;
}