#include <bits/stdc++.h>
#define NMAX 50005
#define inf 9999999
using namespace std;
ifstream in ("bellmanford.in");
ofstream out ("bellmanford.out");

int n,m,cost[NMAX];
tuple<int,int,int> muchii[NMAX];

void afs()
{
    int i;
    for(i=2;i<=n;i++)
        out<<cost[i]<<' ';
}

void bell()
{
    bool ok;
    int p=1,i,x,y,c;
    do
    {
        ok=1;
        for(i=1;i<=m;i++){
            x=get<0>(muchii[i]);
            y=get<1>(muchii[i]);
            c=get<2>(muchii[i]);
            if(cost[x]!=inf and cost[y]>cost[x]+c){
                ok=0;
                cost[y]=cost[x]+c;
            }
        }
        p++;
    }while(ok==0 and p<=n-1);
    if(p==n)
        out<<"Ciclu negativ!";
    else
        afs();
}

int main()
{
    int i;
    in>>n>>m;
    for(i=1;i<=m;i++){
        in>>get<0>(muchii[i])>>get<1>(muchii[i])>>get<2>(muchii[i]);
    }
    for(i=2;i<=n;i++)
        cost[i]=inf;
    bell();
    return 0;
}