#include <iostream>
#include <fstream>
using namespace std;
#define maxn 50001
#define infty 100000000

ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");

struct graf{
int nod;
int dist;
graf* next;
};

struct muchie{
int v1;
int v2;
int w;
};

graf* v[maxn];
int d[maxn];
muchie E[250001];

void add(int a, int b, int cost)
{
    graf* q = new graf;
    q->nod  = b;
    q->dist = cost;
    q->next = v[a];
    v[a] = q;
}

void relax(muchie m)
{
    if(d[m.v1] + m.w < d[m.v2])
        d[m.v2] = d[m.v1] + m.w;
}

int main()
{
    int i,j;
    int n,m;
    fin >> n >> m ;
    for(i=1;i<=m;++i){
    fin >> E[i].v1 >> E[i].v2 >> E[i].w;
    add( E[i].v1, E[i].v2, E[i].w);
    }
    for(i=2;i<=n;++i)
        d[i] = infty;

    for(j=1;j<n;++j){
        for(i=1;i<=m;++i)
            relax(E[i]);
    }

    int check = 1;
    for(i=1;i<=m;++i)
            if(d[E[i].v2] > E[i].w + d[E[i].v1])
                check = 0;

    if(check)
        for(i=2;i<=n;++i)
            fout << d[i] << " ";
        else
            fout << "Ciclu negativ!";
    return 0;
}