#include <cstdio>
#include <vector>
#include <queue>
#include <cstring>
#define inf 2000000000

using namespace std;

struct muchii
{
    int x,c;
}aux;
vector<muchii>v[50010];
vector<muchii>::iterator it;
queue<int>coada;
char incoada[50010];
int nrincoada[50010],sol[50010],n,m,i,x,y,c,cicluneg;

int main()
{
    freopen("bellmanford.in", "r", stdin);
    freopen("bellmanford.out", "w", stdout);
    scanf("%d%d",&n,&m);
    for(i=1;i<=m;i++)
    {
        scanf("%d%d%d",&x,&y,&c);
        aux.x=y;
        aux.c=c;
        v[x].push_back(aux);
    }
    for(i=1;i<=n;i++) sol[i]=inf;
    sol[1]=0;
    coada.push(1);
    incoada[1]=1;
    while(!coada.empty() && !cicluneg)
    {
        x=coada.front();
        coada.pop();
        incoada[x]=0;
        for(it=v[x].begin();it!=v[x].end();it++)
        {
            aux=*it;
            if(sol[aux.x]>sol[x]+aux.c)
            {
                sol[aux.x]=sol[x]+aux.c;
                if(!incoada[aux.x])
                    if(nrincoada[aux.x]>n) cicluneg=1;
                    else
                    {
                        coada.push(aux.x);
                        incoada[aux.x]=1;
                        nrincoada[aux.x]++;
                    }
            }
        }
    }
    if(!cicluneg)
        for(i=2;i<=n;i++) printf("%d ",sol[i]);
    else printf("Ciclu negativ!");
    return 0;
}