#include <fstream>

using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
int n,i,j,f[50005],a[5000][5000],m,d[50005],x,y,dist,mx=999999999,poz,mi,k;
int main()
{
    fin >>n>>m;
    for (i=1;i<=n;i++)
    {
        for (j=1;j<=n;j++)
        {
            if (i==j) a[i][j]=0;
            else a[i][j]=mx;
        }
    }
    for (i=1;i<=m;i++)
    {
        fin >>x>>y>>dist;
        a[x][y]=dist;
    }
    for (i=1;i<=n;i++)
    {
        f[i]=0;
        d[i]=a[1][i];
    }
    for (k=1;k<n;k++)
    {
        poz=0;
        mi=mx;
        for (i=1;i<=n;i++)
        {
            if (d[i]!=0 && d[i]!=mx && f[i]==0 &&d[i]<mi) {mi=d[i];poz=i;}
        }
        f[poz]=1;
        for (i=1;i<=n;i++)
        {
            if (d[poz]+a[poz][i]<d[i]) d[i]=d[poz]+a[poz][i];
        }
    }
    for (i=2;i<=n;i++)
    {
        fout <<d[i]<<" ";
    }
    return 0;
}