#include <iostream>
#include <fstream>
#include <queue>
#include <vector>
#define inf 0x3f3f3f3f
#define Nmax 50005

using namespace std;

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

int N, M, cst[Nmax], viz[Nmax], ok = 1, x, y, c;
queue<int>q;
typedef pair<int,int>pii;
vector<pii>v[Nmax];

void bf(int nod)
{
    for(int i = 0 ; i < v[nod].size(); i++)
    {
        int next = v[nod][i].first;
        int cost = v[nod][i].second;
        if(cst[next] > cst[nod] + cost)
        {
            cst[next] = cst[nod] + cost;
            viz[next] = viz[nod] + 1;
            if(viz[next] == N)
            {
                ok = 0;
                return;
            }
            q.push(next);
        }
    }
}
int main()
{
    fin >> N >> M;
    for(int i = 1; i <= M; i++)
    {
        fin >> x >> y >> c;
        v[x].push_back({y, c});
    }
    for(int i = 1; i <= N; i++)
        cst[i] = inf;
    cst[1] = 0;
    viz[1] = 0;
    q.push(1);
    while(!q.empty() && ok == 1)
    {
        int nd = q.front();
        q.pop();
        bf(nd);
    }

        if(ok == 0)fout << "Ciclu negativ";
    else
        for(int i = 2; i <= N; i++)
            fout << cst[i] << " ";
    return 0;
}