#include <bits/stdc++.h>
using namespace std;

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

const int MAXN = 1e6;
const int INF = 1e8 ;

struct edge{
    int dest, cost;
};
int dist[MAXN], seen[MAXN];
vector <edge> g[MAXN];

int main()
{
    int n, m, flag = 0; fin >> n >> m;
    for(int i = 1; i <= m; ++i){
        int x, y, t; fin >> x >> y>> t;
        g[x].push_back({y, t});
    }

    for(int i = 2; i <= n; ++i) dist[i] = INF;

    deque <int> dq;
    dq.push_back(1);

    while(dq.size()){
        int node = dq.front();
        dq.pop_front();
        seen[node] ++;
        if(seen[node] > n) flag = 1;
        for(auto x : g[node]){
            if(dist[node] + x.cost < dist[x.dest]){
                dist[x.dest] = dist[node] + x.cost;
                dq.push_front(x.dest);
            }
        }
    }

    if(flag) fout << "Ciclu negativ!";
    else {
        for(int i = 2; i <= n; ++i){
            fout << dist[i] << ' ' ;
        }
    }
    return 0;
}