#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;
ifstream f("bellmanford.in");
ofstream g("bellmanford.out");
int t,n,m,i,j,a,b,c,d[200003],cnt[200003];
vector<pair<int,int>>v[200003];
int main()
{   f>>n>>m;
    for (i=1;i<=m;i++){
        f>>a>>b>>c;
        v[a].push_back({c,b});
    }
    priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>>PQ;
    PQ.push({0,1});
    for (i=2;i<=n;i++)d[i]=1e9;
    d[0]=0;
    while(!PQ.empty()){
        tie(a,b)=PQ.top();
        PQ.pop();
        if (a>d[b])continue;
        if (cnt[b]>=n){
            g<<"Ciclu negativ\n";
            exit(0);
        }
        for (auto it : v[b]){
            if (d[it.se]>d[b]+it.fi){
                d[it.se]=d[b]+it.fi;
                PQ.push({d[it.se],it.se});
                cnt[it.se]++;

            }
        }
    }
    for (i=2;i<=n;i++){
        g<<d[i]<<' ';
    }
    g<<'\n';
    return 0;
}