#include <bits/stdc++.h>
#define NMAX 50005
#define INF 0xf3f3f3
using namespace std;
ifstream f("bellmanford.in");
ofstream g("bellmanford.out");
vector< pair<int, int> > G[NMAX];
int n,m;
void citire(){
    f>>n>>m;
    for(int i=1;i<=m;i++){
        int from, to, cost;
        f>>from>>to>>cost;
        G[from].push_back(make_pair(to, cost));
    }
}
deque <int> q;
vector <int> cost(NMAX, INF);
int inq[NMAX];
bitset <NMAX> b(false);
void bellman(){
    q.push_back(1);
    b[1]=true;
    bool ciclu_neg = false;
    cost[1]=0;
    while(!q.empty()&& !ciclu_neg){
        int nod = q.front();
        q.pop_front();
        b[nod]=false;
        if(cost[nod]==INF)continue;
        for(auto it:G[nod]){
            int newnode = it.first;
            int newcost = it.second;
            if(cost[newnode]>cost[nod]+newcost){
                cost[newnode] = cost[nod] + newcost;
                if(!b[newnode]){
                    if(inq[newnode]>n){
                        ciclu_neg=true;
                    }
                    else{
                        inq[newnode]++;
                        q.push_back(newnode);
                        b[newnode] = true;
                    }
                }
            }
        }
    }
    if(ciclu_neg)cout<<"Ciclu negativ!\n";
    else
    for(int i=2;i<=n;i++)g<<cost[i]<<" ";
}
int main()
{
    citire();
    bellman();
    return 0;
}