#include <bits/stdc++.h>
#define Nmax 50001
using namespace std;
ifstream f("bellmanford.in");
ofstream g("bellmanford.out");
struct Node
{
    int vecin;
    int cost;
    Node *leg;
};
Node *G[Nmax];
void ad(int x, int y, int cst)
{
    Node *p=new Node;
    p->cost=cst;
    p->vecin=y;
    p->leg=G[x];
    G[x]=p;
}
struct camp
{
    int inf;
    camp *urm;
};
camp *coada;
camp *in,*sf;
int d[Nmax];
bool inq[Nmax];
int nrap[Nmax];
int n;
bool ok=true;
void Bellman_Ford()
{
    int i,x;
    for(i=2;i<=n;i++)
        d[i]=INT_MAX;
    in=new camp;
    in->inf=1;
    in->urm=NULL;
    sf=in;
    camp *q;
    Node *p;
    nrap[1]++;
    while(in)
    {
        x=in->inf;
        inq[x]=false;
        for(p=G[x];p;p=p->leg)
            if(d[p->vecin]>d[x]+p->cost)
            {
                d[p->vecin]=d[x]+p->cost;
                if(!inq[p->vecin])
                {
                    nrap[p->vecin]++;
                    if(nrap[p->vecin]>n)
                    {
                        ok=false;
                        return;
                    }
                    inq[p->vecin]=true;
                    q=new camp;
                    q->inf=p->vecin;
                    q->urm=NULL;
                    sf->urm=q;
                    sf=q;
                }
            }
        in=in->urm;
    }
}
int main()
{
    int m,i,x,y,w;
    f>>n>>m;
    for(i=1;i<=m;i++)
    {
        f>>x>>y>>w;
        ad(x,y,w);
    }
    Bellman_Ford();
    if(ok)
    {
        for(int i=2;i<=n;i++)
            g<<d[i]<<' ';
    }
    else g<<"Ciclu negativ!";

    return 0;
}