#include <bits/stdc++.h>

using namespace std;

ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");
#define cin fin
#define cout fout

#define N 50005
#define oo 1000000005
int n, m, x, y, cost, f[N], nr[N], d[N];
queue < int > q;
vector < vector < pair < int , int > > > g;

int main()
{
    cin >> n >> m;
    g.resize(n+5);
    for(int i = 1 ; i <= m ; i++)
    {
        cin >> x >> y >> cost;
        g[x].push_back({y,cost});
    }
    for(int i = 2 ; i <= n ; i++)d[i] = oo;
    f[1] = nr[1] = 1;
    q.push(1);
    while(!q.empty())
    {
        int nod = q.front();
        q.pop();
        f[nod] = 0;
        for(int i = 0 ; i < g[nod].size() ; i++)
        {
            int cost = g[nod][i].second;
            int v = g[nod][i].first;
            if(d[v] > cost+d[nod])
            {
                d[v] = cost+d[nod];
                if(f[v] == 0)
                {
                    q.push(v);
                    f[v] = 1;
                    nr[v]++;
                    if(nr[v] == n)
                    {
                        cout << "Ciclu negativ";
                        return 0;
                    }
                }
            }
        }
    }
    for(int i = 2 ; i <= n ; i++)cout << d[i] << " ";
    return 0;
}