#include <fstream>
#include <vector>
#define DIM 50010
#define INF 2000000000

using namespace std;

ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");


int D[DIM], Ciclu[DIM], v[DIM], c[DIM];
int p, u, n, m, x, y, cost;
vector <pair <int, int > > L[DIM];

void citire(){

    fin >> n >> m;

    for(int i = 1; i <= m; i ++)
    {
        fin >> x >> y >> cost;
        L[x].push_back(make_pair(y,cost));
    }


}

void solve(){

    for(int i = 1; i <= n; i ++)
    {
        D[i] = INF;
    }

    D[1] = 0;
    p = 1;
    u = 1;
    c[1] = 1;
    int ok = 1;
    while(p <= u)
    {
        v[c[p]] = 1;

        for(int i = 0; i < L[c[p]].size(); i ++)
        {
            if(D[ L[c[p]][i].first ] > D[ c[p] ]  + L[c[p]][i].second )
            {
                D[ L[c[p]][i].first ] = D[ c[p] ]  + L[c[p]][i].second;
            if(v[ L[c[p]][i].first ] == 0)
            {
                u ++;
                c[u] = L[c[p]][i].first;
                v[ L[c[p]][i].first ] = 1;
                Ciclu[c[p]]++;
                if(Ciclu[c[p]] == n)
                {
                    fout << "Ciclu negativ!";
                    ok = 0;
                }
            }
            }
        if(ok == 0)
            break;
        }
        if(ok == 0)
            break;
        v[c[p ++]] = 0;
    }
    if(ok)
    {
        for(int i = 2; i <= n; i ++)
            fout << D[i] << " ";
    }


}

int main()
{

    citire();
    solve();


    return 0;
}