#include <fstream>
using namespace std;
int a[10002][10002],v[50002],viz[50002];
int main()
{
    ifstream f("dijkstra.in");
    ofstream g("dijkstra.out");
    int n,m,i,j,ii,minn,x,y;
    f>>n>>m;
    for(i=1;i<=m;i++)
    {
        f>>x>>y;
        f>>a[x][y];
    }
    for(i=1;i<=n;i++)
    {
        v[i]=1000000;
        viz[i]=0;
    }
    v[1]=0; ii=1;
    for(i=1;i<=n ;i++)
    {
        minn=1000000;
        for(j=1;j<=n;j++)
        {
            if(v[j]<minn and viz[j]==0)
            {
                minn=v[j];
                ii=j;
            }
        }
        for(j=1;j<=n;j++)
        {
            if(a[ii][j]!=0 and viz[j]==0 and v[j]>v[ii]+a[ii][j])
            {
                v[j]=v[ii]+a[ii][j];
            }
        }
        viz[ii]=1;
    }
    for(i=2;i<=n;i++)
    {
        if(v[i]==1000000)
        {
            g<<"0 ";
        }
        else
        {
            g<<v[i]<<' ';
        }
    }
}