#include<bits/stdc++.h>
#define NMAX 50001
using namespace std;

ifstream f("bellmanford.in");
ofstream g("bellmanford.out");


bitset<NMAX>viz;
vector< pair<int,int> >G[NMAX];
int d[NMAX],p[NMAX];
int cate[NMAX];
int n,m;
bool nuebine=false;

void citire()
{
    f>>n>>m;
    for(int i=1;i<=m;++i)
    {
        int x,y,c;
        f>>x>>y>>c;
        G[x].push_back({y,c});
    }
}

void belmman()
{
    queue<int>Q;
    Q.push(1);
    for(int i=1;i<=n;++i)
    {
        d[i]=INT_MAX;
        p[i]=0;
        viz[i]=false;
    }
    d[1]=0;
    viz[1]=true;
    cate[1]++;
    while(!Q.empty())
    {
        int node=Q.front();
        Q.pop();
        viz[node]=false;
        for(vector< pair<int,int> >::iterator it=G[node].begin();it!=G[node].end();++it)
        {
            int vecin=(*it).first;
            int cost=(*it).second;
            if(d[vecin]>d[node]+cost)
            {
                d[vecin]=d[node]+cost;
                p[vecin]=node;
                if(viz[vecin]==false)
                {
                    Q.push(vecin);
                    viz[vecin]=true;
                    cate[vecin]++;
                    if(cate[vecin]>n)
                    {
                        nuebine=true;
                        return;
                    }
                }
            }
        }
    }
}

int main()
{
    citire();
    belmman();
    if(nuebine==false)
        for(int i=2;i<=n;++i)
            g<<d[i]<<' ';
    else
        g<<"Ciclu negativ!";
}