#include <iostream>
#include <fstream>

#define dim 50005

using namespace std;

const unsigned int inf=2000000000;

ifstream fin ("bellmanford.in");
ofstream fout ("bellmanford.out");

struct graf
{
    int nod,len;
    graf* next;
}*a[dim];

int n,m,d[dim];

int main()
{
    fin>>n>>m;
    for (int i=0;i<n;i++)
    {
        int x,y,cost;
        fin>>x>>y>>cost;
        graf* nou=new graf;
        nou->len=cost;
        nou->nod=y;
        nou->next=a[x];
        a[x]=nou;
    }
    d[1]=0;
    for (int i=2;i<=n;i++)
        d[i]=inf;
    for (int i=1;i<=n-1;i++)
        for (int j=1;j<=n;j++)
        {
            graf* k=a[j];
            while (k!=NULL)
            {
                if (d[j]+k->len<d[k->nod])
                    d[k->nod]=d[j]+k->len;
                k=k->next;
            }
        }
    //verif ciclu negativ
    for (int j=1;j<=n;j++)
    {
        graf* k=a[j];
        while (k!=NULL)
        {
            if (d[j]+k->len<d[k->nod])
            {
                fout<<"Ciclu negativ!";
                return 0;
            }
            k=k->next;
        }
    }
    for (int i=2;i<=n;i++)
        fout<<d[i]<<' ';
    return 0;
}