#include <iostream>
#include <fstream>
#define INF 999999
using namespace std;
ifstream f("bellmanford.in");
ofstream g("bellmanford.out");
int n,m;
struct muchie
{
    int x;
    int y;
    int cost;
}v[250002];
int d[50005];
bool viz[50005];
int c[2000000];
int main()
{
    int i;
    f>>n>>m;
    for(i=1;i<=m;i++)
        f>>v[i].x>>v[i].y>>v[i].cost;
    for(i=2;i<=n;i++)
        d[i]=INF;
    d[1]=0;
    int inc,sf;
    inc=sf=1;
    c[sf]=1;
    sf++;
    while(inc<=sf || inc<=n-1)
    {
        for(i=1;i<=m;i++)
        {
            if(c[inc]==v[i].x)
            {
                if(d[v[i].x]+v[i].cost<d[v[i].y]&&d[v[i].x]!=INF)
                {
                    d[v[i].y]=v[i].cost+d[v[i].x];
                    if(viz[i]==false)
                    {
                        viz[i]=true;
                        c[sf]=v[i].y;
                        sf++;
                    }
                }
            }
        }
        viz[inc]=false;
        inc++;
    }
    /*
    if(ok==0)
    {
        for(i=2;i<=n;i++)
            g<<d[i]<<" ";
    }
    else
        g<<"Ciclu negativ";
    */
    for(i=2;i<=n;i++)
        g<<d[i]<<" ";
    return 0;
}