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

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

int N, M, neg_cycle;
vector<vector<pair<int, int>>>Ad;
vector<int>d;
vector<int>vis;
vector<int>cnt;
queue<int>q;

void Bellman(int node) {
    d[node]=0;
    q.push(node);
    vis[node]=1;
    cnt[node]++;
    while (!q.empty()) {
        int u=q.front();
        q.pop();
        vis[u]=0;
        for (auto &e : Ad[u]) {
            int v = e.first;
            int c = e.second;
            if (d[v] > d[u] + c ) {
                d[v] = d[u] + c;
                if (vis[v] == 0) {
                    vis[v]=1;
                    cnt[v]++;
                    q.push(v);
                    if (cnt[v] > N) {
                        neg_cycle=1;
                        return;
                    }
                }
            }
        }
    }
}

int main() {
    fin>>N>>M;
    Ad.resize(N+1);
    d.assign(N+1, 1e9);
    vis.assign(N+1, 0);
    cnt.assign(N+1, 0);
    int x, y, c;
    while (fin>>x>>y>>c){
        Ad[x].push_back({y, c});
    }
    Bellman(1);
    if (neg_cycle)
        fout<<"Ciclu negativ!";
    else
        for (int i=2;i<=N;i++)
            if (d[i] == 1e9)
                fout<<"-1 ";
            else
                fout<<d[i]<<" ";

    return 0;
}