#include <bits/stdc++.h>

using namespace std;

ifstream cin("bellmanford.in");
ofstream cout("bellmanford.out");

const int NMAX = 5e5 + 5;

int N, M, d[NMAX];
vector <pair<int,int>> l[NMAX];

void read() {
    cin>>N>>M;
    for(int i = 1; i <= M; ++i) {
        int x, y, c;
        cin>>x>>y>>c;
        l[x].push_back({y, c});
    }
}

void solve() {    
    int cnt[NMAX] = {};
    queue <pair<int,int>> q;

    for(int i = 2; i <= N; ++i) {
        d[i] = INT_MAX;
    }

    q.push({1, 0});

    while(!q.empty()) {
        int from = q.front().first;
        int currCost = q.front().second;
        q.pop();

        if(d[from] < currCost) {
            continue;
        }

        ++cnt[from];

        if(cnt[from] > N) {
            cout<<"Ciclu negativ!";
            exit(0);
        }
        
        for(auto k : l[from]) {
            int to = k.first;
            int cost = k.second;
            if(d[from] + cost < d[to]) {
                d[to] = d[from] + cost;
                q.push({to, d[to]});
            }
        }
    }
}

void print() {
    for(int i = 2; i <= N; ++i) {
        cout<<d[i]<<" ";
    }
}

int main() {
    read();
    solve();
    print();
	return 0;
}