#include <iostream>
#include <fstream>
#define INF 1<<30
using namespace std;
ifstream f("bellmanford.in");
ofstream g("bellmanford.out");
int n,m,p,u,i,x,y,z,cn;
int d[50001],c[500001];
struct nod{int vec,cost;
nod *urm;}*v[50001],*q;
void BF()
{
    int x;
    int pus[50001];
    bool e_pus[50001];
    for(int i=1;i<=n;++i)
        d[i]=INF,pus[i]=0,e_pus[i]=false;
    p=u=1;
    c[1]=1;
    e_pus[1]=true;
    d[1]=0;
    while(p<=u)
    {
        x=c[p];
        ++p;
        pus[x]++;
        if(pus[x]==n)
        {
            cn=1;
            return;
        }
        q=v[x];
        while(q!=0)
        {
            int vec=q->vec;
            int cost=q->cost;
            if(d[vec]>d[x]+cost)
            {
                d[vec]=d[x]+cost;
            if(e_pus[vec]==0)
            {
                e_pus[vec]=1;
                c[++u]=vec;
            }
            }
            q=q->urm;
        }
        e_pus[x]=0;
    }
}
int main()
{
    f>>n>>m;
    for(i=1;i<=m;++i)
    {
        f>>x>>y>>z;
        q=new nod;
        q->vec=y;
        q->cost=z;
        q->urm=v[x];
        v[x]=q;
    }
    BF();
    if(cn==1)
        g<<"Ciclu negativ!";
    else
    {
        for(i=2;i<=n;++i)
            g<<d[i]<<" ";
    }

    return 0;
}