#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];
bool inCoada[NMAX];

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


}
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 && distanta[i]<0) {
            fout<<"Ciclu negativ!"<<'\n';
            return 0;
        }
    afis();
    return 0;
}