#include <bits/stdc++.h>
#define MAX 50100
#define INF 1e9

using namespace std;

ifstream f("bellmanford.in");
ofstream g("bellmanford.out");

vector < pair <int, int> > G[MAX];
int n, m;
int d[MAX], s[MAX], cnt[MAX];
queue <int> q;

void dostuff(){
    f >> n >> m;
    for (int i = 1; i <= m; i++){
        int x, y, c;
        f >> x >> y >> c;
        G[x].push_back({y,c});
    }
}

int bf(){
    int nod, nxt, cst;
    d[1] = 0;
    for (int i = 2; i <= n; i++){
        d[i] = INF;
    }
    q.push(1);
    s[1] = 1;
    while(!q.empty()){
        nod = q.front();
        s[nod] = 0;
        q.pop();
        for(int i = 0; i < G[nod].size(); i++)
        {
            nxt = G[nod][i].first;
            cst = G[nod][i].second;
            if(cst + d[nod] < d[nxt]){
                d[nxt] = d[nod] + cst;
                if(s[nxt] == 0){
                q.push(nxt);
                s[nxt] = 1;
                }
                if(++cnt[nxt] > n){
                    return 0;
                }
            }
        }
    }
    return 1;
}

int main()
{
    dostuff();
    bf();
    if (bf()){
        for (int i = 2; i <= n; i++){
            g << d[i] << ' ';
        }
    } else {
        g << "Ciclu negativ!";
    }
    return 0;
}