#include <iostream>
#include <fstream>
#define nrn 50001
#define nrm 250001
#define maxi 999999999
using namespace std;
ifstream f("bellmanford.in");
ofstream g("bellmanford.out");
int t[3][2*nrm], viz[nrn], c[nrn], start[nrn], cost[nrn],n,m,ok,i;
void liste_adiacenta()
{
    int i,x,y,z;
    for (i=1;i<=m;i++)
    {
        f>>x>>y>>z;
        t[0][i]=y;
        t[1][i]=start[x];
        start[x]=i;
        t[2][i]=z;
    }
}
void ford(int nod)
{
    int i,x,y,pi=1, ps=1, k;
    c[pi]=nod;
    for (i=1;i<=n;i++) cost[i]=maxi;
    cost[nod]=0;
    while (ps<=pi)
    {
        k=c[ps];
        x=start[k];
        while (x)
        {
            if (cost[k]+t[2][x]<cost[t[0][x]])
            {
                cost[t[0][x]]=cost[k]+t[2][x];
                if (!viz[t[0][x]])
                    c[++pi]=t[0][x] , viz[t[0][x]]=1;
                else ok=1;
            }
            x=t[1][x];
        }
        ps++;
    }
}
int main()
{
    f>>n>>m;
    liste_adiacenta();
    if (ok==1) g<<"Ciclu negativ!";
    else
    {
        ford(1);
        for (i=2;i<=n;i++)
            g<<cost[i]<<" ";
    }
    return 0;
}