#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];
int c[250000];
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;
    int inc,sf;
    inc=sf=1;
    c[sf]=v[sf].x;
    sf++;
    while(inc<=sf)
    {
        for(i=1;i<=n;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];
                    c[sf]=v[i].y;
                    sf++;
                }
            }
        }
        inc++;
    }
    for(i=2;i<=n;i++)
        g<<d[i]<<" ";
    return 0;
}