#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,m;
    scanf("%d %d",&n,&m);

    for(int i=1; i<= m; i++)
    {
        scanf("%d %d %d",&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);   //distantele de la nodul de start la toate celelalte noduri sunt initializate cu Inf
    cntInQueue.assign(n+1,0);   //numara de cate ori intra fiecare nod in coada
    inQueue.assign(n+1,0);      //marcheaza daca nodul este sau nu in coada
    m[first][first] = 0;        // IMPORTANT ! se initializeaza dinstanta de la nodul de start la el insusi cu 0

    C.push(first);              //coada incepe cu primul nod
    inQueue[first]=true;

    while(!C.empty() && !negativeCicle)
    {
        p=C.front();    //se extrage nodul din coada
        C.pop();
        inQueue[p]=false;   //se demarcheaza

        for(int i=0; i<v[p].size(); i++)    //se incearca optimizarea drumurilor de la nodul de start la
        {                                   // vecinii nodului extras din coada trecand prin acesta
            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;
                if( !inQueue[vecin])        //daca vecinul nu se afla in coada
                {
                    C.push(vecin);          //se adauga
                    inQueue[vecin]=true;    //se marcheaza
                    cntInQueue[vecin]++;    //creste numarul de intrari ale nodului in coada

                    if(cntInQueue[vecin]>n) //daca numarul acesta depaseste n
                        negativeCicle=true; //avem ciclu negativ
                }
            }
        }

    }
    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;
}