#include <bits/stdc++.h>
using namespace std;
using pii = pair<int,int>;
#define pb push_back

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

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

int n, d[N], cnt[N];
vector<pii> e[N];

void read(), bellman();


int main()
{
    fin.tie(0); fout.tie(0);
    ios_base::sync_with_stdio(0);
    
    read();
    bellman();
    for (int i = 2; i <= n; i++) 
        fout << d[i] << ' ';
    
    return 0;
}

void read(){
    int m; fin >> n >> m;
    while (m--){
        int a, b, c; fin >> a >> b >> c;
        e[a].pb({b,c});
    }
}
void bellman(){
    memset(d, oo, sizeof d);
    queue<pii> s; s.push({0, 1}); d[1] = 0;
    while (!s.empty()){
        int from, c; 
        tie(c, from) = s.front(); s.pop();

        for (auto it: e[from]){
            int to, ec; tie(to, ec) = it;
            if (d[to] > c + ec){
                cnt[to]++;
                if (cnt[to] >= n + 2){
                    fout << "Ciclu negativ!";
                    exit(0);
                }
                d[to] = c + ec;
                s.push({d[to], to});
            }
        }
    }
}

//17:22