#include <fstream>

using namespace std;

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

int t[3][250001],start[50001],fr[50001],coada[250001], n, m;
long long mn[50001];
bool ok=1,viza[50001];

void citesc()
{
    int x;
    in>>n>>m;
    for(int i=1; i<=m; i++)
    {
        in>>x>>t[0][i]>>t[2][i];
        t[1][i]=start[x];
        start[x]=i;
    }
}

void atribuire()
{
    for(int i=2; i<=n; i++)
        mn[i]=300000000;
    coada[1]=1;
}

void bellmanford()
{
    int st=1, dr=1, man, x;
    while(st<=dr)
    {
        x=coada[st];
        viza[x]=0;
        man=start[x];
        while(man)
        {
            if(mn[x]+t[2][man]<mn[t[0][man]])
            {
                mn[t[0][man]]=mn[x]+t[2][man];
                if(mn[1]<0)
                {
                    ok=0;
                    return;
                }
                if(viza[t[0][man]]==0)
                {
                    viza[t[0][man]]=1;
                    coada[++dr]=t[0][man];
                    fr[t[0][man]]++;
                    if(fr[t[0][man]]>m-1)
                    {
                        ok=0;
                        return;
                    }
                }
            }
            man=t[1][man];
        }
        st++;
    }
}

void afisare()
{
    if(ok==0)
        out<<"Ciclu negativ!";
    else for(int i=2; i<=n; i++)
        out<<mn[i]<<" ";
}

int main()
{
    citesc();
    atribuire();
    bellmanford();
    afisare();
    return 0;
}