#include <fstream>

using namespace std;
ifstream f("bellmanford.in");
ofstream g("bellmanford.out");
int l[50001];
struct el{int nod; int urm; int cost;};
el a[250001];
int k;
void ad(int x,int y, int z)
{
    k++;
    a[k].nod=y;
    a[k].cost=z;
    a[k].urm=l[x];
    l[x]=k;
}
bool viz[50001];
int lung[50001],stiv[50002];
int main()
{
    int n,m,i,j,x,y,z,maxi=9999999;
    f>>n>>m;
    for(i=1;i<=m;i++)
    {
        f>>x>>y>>z;
        ad(x,y,z);
    }
    for(i=1;i<=n;i++)
        lung[i]=maxi;
    int poz=l[1];
    viz[1]=1;
    stiv[1]=1;
    int sf=1,in=1,nod;
    while(poz)
    {
        nod=a[poz].nod;
        lung[nod]=a[poz].cost;
        sf++;
        stiv[sf]=nod;
        viz[nod]=1;
        poz=a[poz].urm;

    }
    in++;
    int nd;
    while(in<=sf)
    {
        nd=stiv[in];
        poz=l[stiv[in]];
        while(poz)
        {
            nod=a[poz].nod;
            if(viz[nod]==0)
            {
                sf++;
                stiv[sf]=nod;
                viz[nod]=1;
            }
            if(lung[nd]+a[poz].cost<lung[nod])
            {
                lung[nod]=lung[nd]+a[poz].cost;
            }
            poz=a[poz].urm;
        }
        in++;
    }
        poz=l[stiv[sf]];
        nd=stiv[sf];
        int ok=1;
        while(poz)
        {
            nod=a[poz].nod;
            if(lung[nd]+a[poz].cost<lung[nod])
            {
                ok=0;
                poz=0;
            }
            poz=a[poz].urm;
        }
    if(ok==1)
    for(i=2;i<=n;i++)
        g<<lung[i]<<" ";
    else
        g<<"Ciclu negativ!";
    return 0;
}