#include <bits/stdc++.h>

using namespace std;

#define maxx INT_MAX
ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");
int noduri, muchii,x,y,c, dist[50001];
int cnt[50001];
bool trecut[50001];
bool ciclu;
vector<vector<pair<int,int>>> adc;


void Bellman(int nod){
    priority_queue<pair<int,int>> pq;
    pq.push(make_pair(0,nod));
    dist[nod]=0;
    while(!pq.empty()){
        pair<int,int> top = pq.top();
        int c= -top.first;
        int n= top.second;
        pq.pop();
        for(int i=0; i<adc[n].size(); i++){
                int vecin = adc[n][i].second;
                int cos = adc[n][i].first;
            if(dist[vecin]>dist[n]+cos){
                dist[vecin]=dist[n]+cos;
                pq.push(make_pair(-dist[vecin],vecin));
                if(cnt[vecin]>n){
                    ciclu=true;
                    return;
                }
                cnt[vecin]++;
            }
        }
    }
}

int main()
{
    fin>>noduri>>muchii;
    adc.resize(noduri + 1);
    for(int i=0; i<muchii; i++){
        fin>>x>>y>>c;
        adc[x].push_back(make_pair(c,y));
    }

    for(int i=2; i<=noduri; i++){
        dist[i]=maxx;
        trecut[i]=false;
    }
    Bellman(1);
    if (ciclu==false){
        for(int i=2; i<=noduri; i++){
            if(dist[i]==maxx) fout<<0<<' ';
            else fout<<dist[i]<<' ';
        }
    }
    else fout<<"Ciclu negativ!";
    return 0;
}