#include<bits/stdc++.h>
#define N 50010
#define pii pair<int,int>
#define x first
#define y second

using namespace std;

const int inf=1e9;
int n,m;
vector<pii>V[N];
int d[N];
set<pii>S;
int f[N],inS[N];

int main() {
    ifstream cin("bellmanford.in");
    ofstream cout("bellmanford.out");
    cin>>n>>m;
    for (int i=1; i<=m; ++i) {
        int x,y,c; cin>>x>>y>>c;
        V[x].push_back({y,c});
    }

    for (int i=1; i<=n; ++i) d[i]=inf;
    for (auto it:V[1]) d[it.x]=it.y, S.insert({it.y,it.x});
    while (S.size()) {
        int x=S.begin()->y;
        int c=S.begin()->x;
        S.erase(S.begin());
        c=min(c,d[x]); inS[x]=0;
        for (auto it:V[x]) {
            if (d[it.x]>c+it.y) {
                d[it.x]=c+it.y;
                if (!inS[it.x]) {
                     S.insert({c+it.y,it.x}), inS[it.x]=1;
                     f[it.x]++;
                     if (f[it.x]>n+1) return cout<<"Ciclu negativ!",0;
                }
            }
        }
    }
    for (int i=2; i<=n; ++i) {
        if (d[i]==inf) cout<<0<<" ";
        else cout<<d[i]<<" ";
    }

    return 0;
}