#include <cstdio>
#include <iostream>
#include <vector>
#include <queue>

#define nmax 1000000

using namespace std;

long n,m,i,poz,k,x,y,cost,neg;
long ap[50001],q[50001];
long v[3000000];

vector<pair<int,int> > lista[50001];

int main()
{
    freopen("bellmanford.in","r",stdin);
    freopen("bellmanford.out","w",stdout);
    scanf("%ld%ld",&n,&m);
    for (i=1;i<=m;i++)
    {
        scanf("%ld%ld%ld",&x,&y,&cost);
        lista[x].push_back(make_pair(y,cost));
    }
    for (i=1;i<=n;i++) {ap[i]=0; v[i]=nmax; k=1; q[k]=1;}
    poz=1; neg=0; v[1]=0;
    while ((poz<=k) && (neg==0))
    {
        int nod=q[poz]; poz++;
        for (i=0;i<lista[nod].size();i++)
            {
                if (v[lista[nod][i].first]>v[nod]+lista[nod][i].second)
                {
                    v[lista[nod][i].first]=v[nod]+lista[nod][i].second;
                    q[++k]=lista[nod][i].first;
                    ap[lista[nod][i].first]++;
                    if (ap[lista[nod][i].first]>n) {neg=1; break;}
                }
            }
    }
    if (neg==1) printf("Ciclu negativ!");
       else for (i=2;i<=n;i++) {printf("%ld ",v[i]);}
    return 0;
}