#include <bits/stdc++.h>



using namespace std;
ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");
#define INF 1000000000
int n,m;
vector<pair<int,int>>G[50001];
int d[50001],f[50001],viz[50001];
int main(){
    fin>>n>>m;
    while(m--){
        int x,y,cost;
        fin>>x>>y>>cost;
        G[x].push_back({y,cost});
    }
    queue<int>Q;
    Q.push(1);
    for(int i=2;i<=n;i++)
        d[i]=INF;
    int ok=1;
    f[1]=1;
    while(!Q.empty()){
        int nod = Q.front();
        if(ok==0)
            break;
        Q.pop();
        viz[nod]=0;
        f[nod]++;
        if(f[nod]>n)
        {
            ok=-0; break;
        }
        for(auto x : G[nod]){
            int vecin=x.first;
            int cost = x.second;
            if(d[vecin]>d[nod]+cost){

                d[vecin]=d[nod]+cost;
                if(viz[vecin]==0){
                     Q.push(vecin);
                     viz[vecin]=1;
                }
            }

        }
    }
    if(ok==0)
        fout<<"Ciclu negativ!";
    else
        for(int i=2;i<=n;i++)
            fout<<d[i]<<" ";

    return 0;
}