#include <iostream>
#include <fstream>
using namespace std;
ifstream f ("dijkstra.in");
ofstream g ("dijkstra.out");
int a[5000][5000], d[50005], s[50005], t[50005], n, m, minn, poz, x;
const int oo=20005;
void dijkstra()
{
    for(int p=1; p<n; p++)
    {
        minn=oo;
        for(int i=1; i<=n; i++)
    {
        if(minn>d[i] && s[i]==0 && d[i]!=0)
        {
            minn=d[i];
            poz=i;
        }
        else if (minn=d[i] && s[i]==0 && d[i]!=0)
        {
            poz=i;
        }
    }
    s[poz]=1;
    for(int i=1; i<=n; i++)
        if(i!=poz && i!=x && d[poz]+a[poz][i]<d[i])
    {
        d[i]=d[poz]+a[poz][i];
        t[i]=poz;
    }
    }
}
int main()
{
    int i, p,c, q;
    f>>n>>m;
    for(p=1; p<=n; p++)
        for(q=1; q<=n; q++)
            {
                if(p!=q) a[p][q]=20005;
            }
    for(i=1; i<=m; i++)
       {
        f>>p>>q>>c;
        a[p][q]=c;
       }
    x=1;
    for(i=1; i<=n; i++)
    {
        d[i]=oo;
    }
    s[x]=1;
    for(i=1; i<=n; i++)
    {
        if(a[x][i]!=0)
        {
            d[i]=a[x][i];
            if(a[x][i]!=oo)
                t[i]=x;
        }
        if(x==i) d[i]=0;
    }
    minn=d[1];
    poz=1;
    dijkstra();
    for(i=2; i<=n; i++)
        g<<d[i]<<" ";


    return 0;
}