#include <fstream>

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