#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[50003],cnt[50003],inq[50003];
vector<pair<int,int>>v[50003];
signed main()
{   f>>n>>m;
    for (i=1;i<=m;i++){
        f>>a>>b>>c;
        v[a].push_back({c,b});
    }
    queue<pair<int,int>>PQ;
    PQ.push({0,1});
    for (i=2;i<=n;i++)d[i]=1e12;
    d[1]=0;

    while(!PQ.empty()){
        tie(a,b)=PQ.front();
        PQ.pop();
        inq[b]=0;

        for (auto it : v[b]){
            if (d[it.se]>d[b]+it.fi){
                d[it.se]=d[b]+it.fi;
                if (!inq[it.se]){
                    PQ.push({d[it.se],it.se});
                    inq[it.se]=1;
                    cnt[it.se]++;
                }

                if (cnt[it.se]>n+1){
                    g<<"Ciclu negativ!\n";
                    exit(0);
                }
            }
        }
    }
    for (i=2;i<=n;i++){
        g<<d[i]<<' ';
    }
    g<<'\n';
    return 0;
}