#include <iostream>
#include <fstream>
using namespace std;
#define INF 50000000
ifstream in("bellmanford.in");
ofstream out("bellmanford.out");
struct nod{
int inf;
int c;
nod * next;};
nod * graf[50005];
void add(int x,int y,int c)
{
    nod * p;
    p=new nod;
    p->inf=y;
    p->c=c;
    p->next=graf[x];
    graf[x]=p;
}
void citire(int &n,int &m)
{
    in>>n>>m;
    int i,x,y,c;
    for(i=1;i<=m;i++)
    {
        in>>x>>y>>c;
        add(x,y,c);
    }
}
void afisare(int n)
{
    nod * p;
    int i;
    for(i=1;i<=n;i++)
    {
        p=graf[i];
        out<<i<<' ';
        while(p)
        {
            out<<p->inf<<' '<<p->c<<"   ";
            p=p->next;
        }
        out<<'\n';
    }
}
int distanta[50002];
void afisare2(int n)
{
    int i;
    for(i=2;i<=n;i++)
        out<<distanta[i]<<' ';
    out<<'\n';
}
void bellman_ford(int n)
{
    int ok=1;
    int i;
    for(i=1;i<=n;i++)
        distanta[i]=INF;
    distanta[1]=0;
    int j=1;
    while(j<=n-1 and ok)
    {
        ok=0;
        for(i=1;i<=n;i++)
        {
            nod * p;
            p=graf[i];
            while(p)
            {
                if(distanta[p->inf]>p->c+distanta[i])
                {distanta[p->inf]=p->c+distanta[i];ok=1;}
                p=p->next;
            }
        }
        j++;
    }
    if(ok)
    out<<"Ciclu negativ!";
    else
        afisare2(n);

}
int main()
{
    int n,m;
    citire(n,m);
    bellman_ford(n);
    return 0;
}