#include <bits/stdc++.h>
const int NMAX = 50005;
const int INF = 0x7fffffff;
using namespace std;

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

struct Muchie {
    int v;
    int cost;
};

vector<Muchie> vecini[NMAX];
int distanta[NMAX], n, ciclu[NMAX];

void bellmanFord(int s) {
    int u;
    for(u=1; u<=n; u++)
        distanta[u]=INF;
    queue<int> q;
    distanta[s]=0;
    q.push(s);
    while(!q.empty()){
        u=q.front();
        ciclu[u]++;
        if(ciclu[u]==n)
            return;
        q.pop();
        for(Muchie e : vecini[u]) {
            if(distanta[e.v]>distanta[u]+e.cost) {
                distanta[e.v]=distanta[u]+e.cost;
                q.push(e.v);
            }
        }
    }
}


int main() {
    int m, i, x, y, c;
    fin>>n>>m;
    for(i=1; i<=m; i++) {
        fin>>x>>y>>c;
        vecini[x].push_back({y, c});
    }
    bellmanFord(1);
    for(i=1; i<=n; i++)
        if(ciclu[i]>=n) {
            fout<<"Ciclu negativ!"<<'\n';
            return 0;
        }
    for(int i=2; i<=n; i++)
        fout<<distanta[i]<<" ";
    return 0;
}