#include <bits/stdc++.h>
#define MAX 60000

using namespace std;

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

int d[MAX], n, m;
vector < pair <int, int> > G[MAX];
queue <int> Q;
int nr[MAX];
bool inQ[MAX];
void init()
{
    int i;
    for(i = 1; i <= n; i ++) d[i] = INT_MAX;
    d[1] = 0;
}
bool bellman()
{
    int i, nod, x;
    bool negativ = false;
    Q.push(1);
    while(!Q.empty() && !negativ)
    {
        nod = Q.front();
        Q.pop();
        inQ[nod] = false;
        x=G[nod].size();
        for(i = 0; i < x && !negativ; i ++)
            if(d[G[nod][i].first] > d[nod] + G[nod][i].second)
            {
                d[G[nod][i].first] = d[nod] + G[nod][i].second;
                if(!inQ[G[nod][i].first])
                {
                    if(nr[G[nod][i].first] < n)
                    {
                        Q.push(G[nod][i].first);
                        nr[G[nod][i].first] ++;
                        inQ[G[nod][i].first] = true;
                    }
                    else negativ = true;
                }
            }
    }
    return negativ;
}
int main()
{
    int x, y, c, i;
    fin >> n >> m;
    for(i = 1; i <= m; i ++)
    {
        fin >> x >> y >> c;
        G[x].push_back(make_pair(y, c));
    }
    init();
    if(bellman()) fout << "Ciclu negativ!\n";
    else
        for(i = 2; i <= n; i ++)
        fout << d[i] << " ";
    return 0;
}