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

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

const int N = 5e4 + 5;
const int oo = 0x3f3f3f3f;

int n, m, cnt[N], cst[N];
vector<pair<int, int>> v[N];
queue<pair<int, int>> q;

void init(), bellmanford();

int main()
{
    init();
    bellmanford();
    for (int i = 2; i <= n; i++) 
        g << cst[i] << ' ';
        
    return 0;
}

void init(){
    int x, y, c;
    f >> n >> m;
    for (; m; m--){
        f >> x >> y >> c;
        v[x].push_back({y, c});
    }
    memset(cst, oo, sizeof cst);
}
void bellmanford(){
    cst[1] = 0; q.push({1, 0});
    while (!q.empty()){
        int from, c; 
        tie(from, c) = q.front(); q.pop();
        for (auto it: v[from]){
            int to, cm; tie(to, cm) = it;
            if (c + cm < cst[to]){
                cst[to] = c + cm;
                cnt[to]++;
                if (cnt[to] == n + 1){
                    g << "Ciclu negativ!";
                    exit(0);
                }
                q.push({to, cst[to]});
            }
        }
    }
}