#include <fstream>

using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
int n,m,x,y,cost,c[3000][3000],t[3000],u[3000],INF=200000000,d[3000];
void citire()
{
    int i,j;
    f>>n>>m;
    for (i=1;i<=n;i++)
    {
        for (j=1;j<=n;j++)
        {
            if (i==j)
            {
                c[i][j]=0;
            }
            else
            {
                c[i][j]=INF;
            }
        }
    }
    for (i=1;i<=m;i++)
    {
        f>>x>>y>>cost;
        c[x][y]=cost;
    }
}
void djikstra(int s)
{
    int mini,i,k,x;
    for (i=1;i<=n;i++)
    {
        d[i]=INF;
    }
    d[s]=0;
    t[s]=0;
    for (k=1;k<=n;k++)
    {
        mini=INF;
        for (i=1;i<=n;i++)
        {
            if (!u[i]&&d[i]<mini)
            {
                mini=d[i];
                x=i;
            }
        }
        if (mini==INF)break;
        u[x]=1;
        for (i=1;i<=n;i++)
        {
            if (d[x]+c[x][i]<d[i])
            {
                d[i]=d[x]+c[x][i];
                t[i]=x;
            }
        }
    }
}
void afis(int i)
{
    if (t[i]!=0)
    {
        afis(t[i]);
    }
    g<<i<<" ";
}
int main()
{int i;
    citire();
    djikstra(1);
    for (i=2;i<=n;i++)
    {
        if (d[i]!=INF)
        {
             g<<d[i]<<" ";
        }
        else
        {
            g<<"0"<<" ";
        }
    }
    return 0;
}