#include <bits/stdc++.h>
#define INF 10000001
using namespace std;
ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");
int n,m,x,y,c;
vector<pair<int,int> >g[50001];
queue<int>q;
int d[50001],viz[50001],inq[50001];
int main(){
 fin>>n>>m;
 for(int i=1;i<=m;i++){
    fin>>x>>y>>c;
    g[x].push_back({y,c});
 }
 for(int i=1;i<=n;i++)d[i]=INF;
 d[1]=0;
 viz[1]=1;
 inq[1]++;
 q.push(1);
 int ok=1;
 while(!q.empty()&&ok){
    int nod=q.front();
    q.pop();
    viz[nod]=0;
    for(auto i:g[nod]){
        int vecin=i.first;
        int cost=i.second;
        if(d[vecin]>d[nod]+cost){
            d[vecin]=d[nod]+cost;
            inq[vecin]++;
            if(inq[vecin]>n){
                ok=0;
            }
            if(!viz[vecin]){
            viz[vecin]=1;
            q.push(vecin);
           }
        }
    }
 }
 if(ok==0)fout<<"Ciclu negativ!";
 else{
    for(int i=2;i<=n;i++)fout<<d[i]<<' ';
 }
}