#include <iostream>
#include <fstream>
#define N 50005
#define M 5*N
#define oo 999999999
#include <vector>
#include <algorithm>

using namespace std;

ifstream x("bellmanford.in");
ofstream y("bellmanford.out");

long n,m,i,j,k,left,right,cost[N],f[N];

vector <long> v[N];
vector <pair<long,long> >h;

struct elem
{
    long st,dr,c;
}e[M];

void ini()
{
    long i;
    cost[1]=0;
    for(i=2;i<=n;i++)
        cost[i]=oo;

    h.push_back(make_pair(0,1));
    make_heap(h.begin(),h.end());
}

void ford()
{
    pair<long,long> per;
    long i,j,nod,poz;
    long long pas=0;
    while(h.size() && pas<=1LL*n*m)
    {
        pas++;
        pop_heap(h.begin(),h.end());
        per=h.back();
        h.pop_back();
        nod=per.second;
        f[nod]=0;
        for(j=0;j<v[nod].size();j++)
        {
            poz=v[nod][j];
            if(cost[e[poz].st]+e[poz].c<cost[e[poz].dr])
            {
                cost[e[poz].dr]=cost[e[poz].st]+e[poz].c;
                if(!f[e[poz].dr])
                {
                    f[e[poz].dr]=1;
                    h.push_back(make_pair(-cost[e[poz].dr],e[poz].dr));
                    push_heap(h.begin(),h.end());
                }
            }
        }
    }
}

bool check_neg()
{
    long i;
    for(i=1;i<=m;i++)
        if(cost[e[i].st]+e[i].c<cost[e[i].dr])
            return 1;
    return 0;
}

int main()
{
    x>>n>>m;
    for(k=1;k<=m;k++)
    {
        x>>e[k].st>>e[k].dr>>e[k].c;
        v[e[k].st].push_back(k);
    }
    ini();
    ford();
    if(check_neg())
        y<<"Ciclu negativ";
    else
        for(i=2;i<=n;i++)
            y<<cost[i]<<" ";
    x.close();
    y.close();
    return 0;
}