#include <iostream>
#include <fstream>
#include <queue>
#include <vector>
#define nmax 50005
#define Inf ((1<<31)-1)
using namespace std;

vector<bool> inQueue;
vector<int> cntInQueue;
vector< pair<int,int > >v[nmax];
vector<int> m[nmax];
int n;

void citire()
{
    int a,b,c,nn;
    cin>>n>>nn;

    for(int i=1;i<= nn;i++)
    {
        cin>>a>>b>>c;
        v[a].push_back(make_pair(b,c));
    }
}


bool bellmanFord(int first)
{
    queue<int> C;
    int p;
    bool negativeCicle=false;
    m[first].assign(n+1,Inf);
    cntInQueue.assign(n+1,0);
    inQueue.assign(n+1,0);
    m[first][first] = 0;
    C.push(first);
    inQueue[first]=true;
    while(!C.empty() && !negativeCicle)
    {
        p=C.front();
        C.pop();
        inQueue[p]=false;
        for(int i=0; i<v[p].size(); i++)
        {
            int vecin=v[p][i].first;
            int cost=v[p][i].second;
            if(m[first][p]+cost < m[first][vecin])
            {
                m[first][vecin]=m[first][p]+cost;
                cntInQueue[vecin]++;
                if(cntInQueue[vecin]>n)
                    negativeCicle=true;

                if( !inQueue[vecin])
                {
                    C.push(vecin);
                    inQueue[vecin]=true;
                }
            }
        }

    }
    return negativeCicle;
}

int main()
{
    freopen("bellmanford.in","rt",stdin);
    freopen("bellmanford.out","wt",stdout);
    citire();
    if(!bellmanFord(1))
        for(int i=2;i< m[1].size();i++)
            cout<<m[1][i]<<' ';
    else
        cout<<"Ciclu negativ!";
    return 0;
}