#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
using namespace std;

#define INF 1000000000

vector <int> nod[50001];
vector <int> cost[50001];
vector <bool> isq;
queue <int> coada;

int n,m,a,b,c,d[50001],cont[50001];

int main()
{
    freopen("bellmanford.in","r",stdin);
    freopen("bellmanford.out","w",stdout);
    scanf("%d %d",&n,&m);
    isq.resize(n+1,false);
    for(int k=1;k<=n;k++)
        d[k]=INF;
    for(int k=1;k<=m;k++)
    {
        scanf("%d %d %d",&a,&b,&c);
        nod[a].push_back(b);
        cost[a].push_back(c);
    }
    coada.push(1);
    d[1]=0;
    isq[1]=true;
    int ok=1;
    while(!coada.empty() && ok)
    {
        a=coada.front();
        isq[coada.front()]=false;
        coada.pop();
        for(int k=0;k<nod[a].size();k++)
        {
            if(d[nod[a][k]] > d[a] + cost[a][k])
            {
                d[nod[a][k]]=d[a]+cost[a][k];
                if(!isq[nod[a][k]])
                {
                    coada.push(nod[a][k]);
                    isq[nod[a][k]]=true;
                }
                cont[nod[a][k]]++;
            }
            if(cont[nod[a][k]]==n)
                ok=0;
        }
    }
    if(ok)
        for(int k=2;k<=n;k++)
            printf("%d ",d[k]);
    else
        printf("Ciclu negativ!");
    printf("\n");
    return 0;
}