#include <iostream>
#include <fstream>
#include <queue>
#include <vector>
using namespace std;
ifstream fin ("bellmanford.in");
ofstream fout ("bellmanford.out");
int n,i,j,viz[50005],cate[50005],m,x,y,cost,el,d[50005],vecin,negativ;
queue <int> q;
vector <int> liste[50005];
vector <int> listeval[50005];
void actual(int nod)
{
    for(int i=0;i<=cate[nod]-1;i++)
    {
        vecin=liste[nod][i];
        if(d[nod]+listeval[nod][i]<d[vecin])
        {
            d[vecin]=d[nod]+listeval[nod][i];
            if(viz[vecin]==0)
            {
                q.push(vecin);
                viz[vecin]=1;
            }
        }
    }
}
void init()
{
    for(int i=0;i<=n;i++) d[i]=1999999999;
}
int main()
{
    fin>>n>>m;
    for(i=1;i<=m;i++)
    {
        fin>>x>>y>>cost;
        liste[x].push_back(y);
        listeval[x].push_back(cost);
        cate[x]++;
    }
    q.push(1);
    viz[1]=1;
    init();
    d[1]=0;
    while(q.empty()==0)
    {
        ///luam primul nod din coada, vedem daca schimba distanta pentru vecinii lui
        ///daca pentru un nod o schimba, actualizam distanta mai mica
        ///daca nodul pentru care a schimbat nu era deja in coada, il adaugam la final
        el=q.front();
        actual(el);
        q.pop();
    }
    for(i=1;i<=n and negativ==0;i++)
    {
        for(j=0;j<=cate[i]-1 and negativ==0;j++)
        {
            if(d[i]+listeval[i][j]<d[liste[i][j]])
            {
                negativ=1;
            }
        }
    }
    if(negativ==1) fout<<"Ciclu negativ!";
    else
    {
        for(i=2;i<=n;i++)
        {
            fout<<d[i]<<' ';
        }
    }
    return 0;
}