#include <iostream>
#include <fstream>
#include <queue>
using namespace std;
#define N 50001
#define M 250001
#define inf 999999999
ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");

int n, m, x, y, cst, k, ciclu_neg;
int t[3][M], viz[N], cost[N], start[N];
queue <int> c;

void bellman_ford()
{
    int man, om;
    c.push(1);
    viz[1] = 1;
    while( !c.empty() && !ciclu_neg)
    {
        om = c.front();
        man = start[om];
        viz[om] = 0;
        while( man )
        {
            if(cost[om] + t[2][man] < cost[t[0][man]])
            {
                cost[t[0][man]] = cost[om] + t[2][man];
                if( !viz[t[0][man]])
                {
                    c.push(t[0][man]);
                    viz[t[0][man]] = 1;
                }
            }
            man = t[1][man];
        }
        c.pop();
    }
}

int main()
{
    fin >> n >> m;
    while(fin >> x >> y >> cst)
    {
        k++;
        t[0][k] = y;
        t[1][k] = start[x];
        t[2][k] = cst;
        start[x] = k;
    }

    for(int i=2; i<=n; i++)
        cost[i] = inf;
    cost[1] = 0;

    bellman_ford();

    for(int i=2; i<=n; i++)
        fout << cost[i] << " ";
//    if( !ciclu_neg)
//        for(int i=2; i<=n; i++)
//            fout << cost[i] << " ";
//    else
//        fout << "Ciclu negativ!";
    return 0;
}