#include <bits/stdc++.h>
using namespace std;
ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");
const int NMAX = 5e4, INF = 5e8;
struct edge {
    int node, cost;
};

vector<edge> edges[NMAX];
queue<int> q;
int dist[NMAX], marked[NMAX], cnt[NMAX], n, stg;

void bellmanford(int source) {
    for(int i = 0; i < n; i++) {
        marked[i] = false;
        dist[i] = INF;
    }
    dist[source] = 0;
    cnt[source]++;
    q.push(source);
    marked[source] = true;
    while(!q.empty() && cnt[q.front()] < n) {
        for(auto neighbour : edges[q.front()]) {
            if(dist[neighbour.node] > dist[q.front()] + neighbour.cost) {
                dist[neighbour.node] = dist[q.front()] + neighbour.cost;
                cnt[neighbour.node]++;
                if(marked[neighbour.node] == false) {
                    q.push(neighbour.node);
                    marked[neighbour.node] = true;
                }
            }
        }
        marked[q.front()] = false;
        q.pop();
    }
    if(!q.empty())
        stg = 1;
}

int main() {
    int m, a, b, c;
    fin >> n >> m;
    for(int i = 0; i < m; i++) {
        fin >> a >> b >> c;
        edges[a - 1].push_back({b - 1, c});
    }
    stg = 0;
    bellmanford(0);
    if(stg == 1)
        fout << "Ciclu negativ!";
    else {
        for(int i = 1; i < n; i++)
            fout << dist[i] << " ";
    }
    return 0;
}