#include <bits/stdc++.h>

using namespace std;
ifstream f("bellmanford.in");
ofstream g("bellmanford.out");

int N, M, x, y, c;
int C[50005];

vector < pair < int, int > > G[50005];
queue <int> Q;

void BF()
{
   Q.push(1);
    for(int i = 1; i <= N; i ++)
    {
        queue <int> S;
        bool changed = 0;
        while(!Q.empty())
        {
            int nod = Q.front();
            Q.pop();
            for(int j = 0; j < G[nod].size(); j ++)
            {
                int nodnou = G[nod][j].first;
                int cost = G[nod][j].second;
                if(C[nod] + cost < C[nodnou])
                {
                    changed = 1;
                    C[nodnou] = C[nod] + cost;
                    S.push(nodnou);
                }
            }
        }
        Q = S;
        if(!changed)
            return;
        if(i == N && changed)
        {
            g << "Ciclu negativ!";
            exit(0);
        }
    }
}

int main()
{
    f >> N >> M;
    for(int i = 1; i <= M; i ++)
    {
        f >> x >> y >> c;
        G[x].push_back( {y, c} );
    }

    for(int i = 1; i <= N; i ++)
        C[i] = 1000000000;
    C[1] = 0;
    BF();
    for(int i = 2; i <= N; i ++)
        g << C[i] << " ";
    return 0;
}