#include <bits/stdc++.h>

#define f first
#define s second

using namespace std;

ifstream F("bellmanford.in");
ofstream G("bellmanford.out");

int n, m, x, y, c, d[50005], ap[50005];
bitset<50005> v;
queue<int> q;
vector<pair<int, int> > a[50005];
const int inf = 1 << 30;

int main()
{
    F >> n >> m;
    for(int i = 1; i <= m; ++ i){
        F >> x >> y >> c;
        a[x].push_back({y, c});
    }
    for(int i = 2; i <= n; ++ i) d[i] = inf;
    q.push(1);
    v[1]=1;
    while(!q.empty()){
        x = q.front();
        q.pop();
        v[x] = 0;
        for(auto it: a[x]){
            if(d[it.f] > d[x]+it.s){
                d[it.f] = d[x]+it.s;
                if(!v[it.f]) v[it.f] = 1, q.push(it.f);
                if(++ap[it.f]>n){
                    G << "Ciclu negativ!";
                    return 0;
                }
            }
        }
    }
    for(int i = 2; i <= n; ++ i) G << d[i] << " ";
    return 0;
}