#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <bitset>
using namespace std;
const int NMAX = 50050;
ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");
int n,m;
int D[NMAX];
int C[NMAX];
vector<pair<int,int>> G[NMAX];
bitset<NMAX> inCoada(false);
queue<int> coada;
int main()
{
    fin>>n>>m;
    for(int i=0; i<m; i++)
    {
        int x,y,c;
        fin>>x>>y>>c;
        G[x].push_back({y,c});
    }
    fill(D,D+n+10,1000000);
    D[1]=0,coada.push(1),inCoada[1].flip(),C[1]++;
    bool neg = false;
    while(coada.size()&&(!neg))
    {

        int j = coada.front();
        coada.pop();
        inCoada[j]=false;
        for(int i = 0; i<G[j].size(); i++)
        {
            int vecin = G[j][i].first;
            int cost  = G[j][i].second;
            if(D[vecin]>D[j]+cost)
            {
                D[vecin]=D[j]+cost;
                if(!inCoada[vecin]){
                    if(C[vecin]>n)
                        neg = true;
                    else
                    {
                        coada.push(vecin);
                        inCoada[vecin]=true;
                        C[vecin]++;
                    }
                }
            }
        }
    }
    if(neg)
        fout<<"Ciclu negativ!"<<" ";
    else
        for(int i = 2;i<=n;i++)
            fout<<D[i]<<" ";
return 0;
}