#include <fstream>

using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
int a[1001][1001],viz[50001],d[50001],i,j,c,n,m,x,y,nod,minim;
int main()
{
    f>>n>>m;
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
        a[i][j]=10001;
    for(i=1;i<=m;i++)
    {
        f>>x>>y>>c;
        a[x][y]=c;
    }
    for(i=1;i<=n;i++)
        d[i]=a[1][i];
    viz[1]=1;
    for(i=1;i<n;i++)
    {
        minim=99999;
        for(j=2;j<=n;j++)
        if(d[j]<minim&&viz[j]==0){minim=d[j];nod=j;}
        viz[nod]=1;
        for(j=2;j<=n;j++)
            if(viz[j]==0&&d[nod]+a[nod][j]<d[j])d[j]=d[nod]+a[nod][j];
    }
    for(i=2;i<=n;i++)
    {if(d[i]==10001)g<<0<<" ";
    else g<<d[i]<<" ";
    }
    return 0;
}