#include <fstream>
using namespace std;
int a[20002][20002],v[50002],viz[50002];
int main()
{
    ifstream f("dijkstra.in");
    ofstream g("dijkstra.out");
    int n,m,i,j,q,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;
    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];
                q=j;
            }
        }
        for(j=1;j<=n;j++)
        {
            if(a[q][j]!=0 and v[q]+a[q][j]<v[j] and viz[j]==0)
            {
                v[j]=v[q]+a[q][j];
            }
        }
        viz[q]=1;
    }
    for(i=2;i<=n;i++)
    {
        g<<v[i]<<' ';
    }
}