#include <bits/stdc++.h>
#define MAX 50005
#define INFINIT 50005000
using namespace std;
ifstream fin ("bellmanford.in");
ofstream fout("bellmanford.out");
typedef pair <int, int> pairINT;

int n,Dist[MAX],Viz[MAX];
vector <pairINT> Nod[MAX];
priority_queue <pairINT, vector <pairINT>, greater <pairINT>> pQ;
bool negativ;

void read();
void BellmanFord();
void ans();

int main(){
    read();
    BellmanFord();
    ans();
    return 0;
}
void BellmanFord(){
    int i,x,cost,k;
    pQ.push(make_pair(0,1));

    for(i=2;i<=n;++i)
        Dist[i]=INFINIT;

    while(!pQ.empty()){
        cost=pQ.top().first;
        x=pQ.top().second;
        pQ.pop();

        if(cost>Dist[x])
            continue;

        for(auto it:Nod[x]){
            if(cost+it.first<Dist[it.second]){
                pQ.push(make_pair(cost+it.first,it.second));
                Dist[it.second]=cost+it.first;
                ++Viz[it.second];
                if(Viz[it.second]>Nod[it.second].size()){
                    negativ=1;
                    return;
                }
            }
        }
    }
}
void read(){
    int i,m,x,y,c;
    fin>>n>>m;
    for(i=0;i<m;++i){
        fin>>x>>y>>c;
        Nod[x].push_back(make_pair(c,y));
//        Nod[y].push_back(make_pair(c,x));
    }
}
void ans(){
    int i;
    if(negativ){
        fout<<"Ciclu negativ!";
        return;
    }

    for(i=2;i<=n;++i){
        fout<<Dist[i]<<' ';
    }
}