#include <bits/stdc++.h>
#define int long long
#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];
signed 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]=1e12;
    d[1]=0;
    //cnt[1]++;
    while(!PQ.empty()){
        tie(a,b)=PQ.top();
        PQ.pop();
        if (a>d[b])continue;
        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]++;
                if (cnt[it.se]>n+1){
                    cout<<"Ciclu negativ!\n";
                    exit(0);
                }
            }
        }
    }
    for (i=2;i<=n;i++){
        g<<d[i]<<' ';
    }
    g<<'\n';
    return 0;
}