#include <iostream>
#include <fstream>

using namespace std;

ifstream f("dijkstra.in");
ofstream g("dijkstra.out");

#define inf 1000000

int n, m, c[10000][10000], d[50001], tata[50001], s[50001];

void citire()
{
    int a, b, di, i, j;
    f>>n>>m;

    for(i=1; i<=n; i++)
        for(j=1; j<=n; j++)
            if(i!=j)
                c[i][j]=inf;

    for(i=1; i<=m; i++)
    {
        f>>a>>b>>di;
        c[a][b]=di;
    }

}

void djaistra(int st)
{
    int i, ok, k, minn=inf;

    for(i=1; i<=n; i++)
    {
        d[i]=c[st][i];
        if(c[st][i]!=0 && c[st][i]!=inf)
            tata[i]=st;
    }
    ok=1;
    s[st]=1;
    while(ok)
    {
        minn=inf;
        for(i=1; i<=n; i++)
            if(d[i]<minn && s[i]==0)
            {
                minn=d[i];
                k=i;
            }
        if(minn!=inf)
        {
            s[k]=1;
            for(i=1; i<=n; i++)
            {
                if(d[i] > d[k] + c[k][i])
                {
                    d[i]=d[k]+ c[k][i];
                    tata[i]=k;
                }
            }
        }
        else
            ok=0;
    }

}

void drum(int h)
{
    int i;
    for(i=2;i<=n;i++)
        if(d[i]!=inf)
            g<<d[i]<<" ";
        else
            g<<0<<" ";


}
int main()
{
    citire();

    djaistra(1);

    drum(n);

    return 0;
}