#include<iostream>
#include<fstream>
#define DN 50050
#define DM 25050
using namespace std;
fstream fin("bellmanford.in",ios::in), fout("bellmanford.out",ios::out);

int muchii[DM][3],n,m;
int d[DN],p[DN];

bool bellman_ford()
{
    int i,j,u,v,c,cicluNegativ=0;
    for(i=1;i<=n;i++)
    {
        d[i]=DM;    //infinit
        p[i]=-1;
    }
    d[1]=0;

    for(i=1;i<DN;i++)   //repeta operatia de n-1 ori
    {
        for(j=1;j<=DM;j++)  //ia fiecare muchie m ori
        {
            u=muchii[j][0];     //nodul u
            v=muchii[j][1];     //nodul v
            c=muchii[j][2];     //costul dintre u si b
            if(d[v]>d[u]+c)     //se incearca relaxare
            {
                d[v]=d[u]+c;
                p[v]=u;
            }
        }
    }
    for(j=1;j<=DM;j++)
    {
        u=muchii[j][0];     //nodul u
        v=muchii[j][1];     //nodul v
        c=muchii[j][2];     //costul dintre u si b
        if(d[v]>d[u]+c)     //se incearca relaxare
        {
            return false;   //ii bai daca s-o reusit relaxare
        }
    }
    return true;
}


int main()
{
    int i,x,y,c;
    fin>>n>>m;
    for(i = 1; i <= m; i++)
        fin>>muchii[i][0]>>muchii[i][1]>>muchii[i][2];

    if(bellman_ford()==false)
    {
        fout<<"Ciclu negativ!\n";
    }
    else
    {
        for(i=2;i<=n;i++)
            fout<<d[i]<<" ";
        fout<<"\n";
    }
    return 0;
}