#include <vector>
#include <queue>
#include <fstream>
#include <bits/stdc++.h>
#include <iostream>
#define INF 100000000
#define Nmax 50001


using namespace std;

ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");

vector< pair<int,int > >graf[Nmax];
int drum[Nmax];
queue<int>q;
bool cicle=false,viz[Nmax];
int cnt[Nmax],n,m;

void BellmanFord(){
    int nod, point, distance;
        while(!q.empty()&& !cicle)
        {
            nod=q.front();
            q.pop();
            viz[nod]=false;
            cout<<nod<<endl;
            for(int i=0;i<graf[nod].size();i++)
            {
                point = graf[nod][i].first;
                distance = graf[nod][i].second;
                if(drum[point] > drum[nod]+distance)
                {
                    drum[point] = drum[nod]+distance;
                    if(!viz[point])
                    {
                        viz[point]=true;
                        q.push(point);
                        cnt[point]++;
                        if(cnt[point] > n)
                            cicle=true;

                    }
                }
            }
        }
}



int main()
{
    int i,nod,node,cost;
    fin>>n>>m;
    for(i=1;i<=m;i++)
        {
            fin>>nod>>node>>cost;
            graf[nod].push_back(make_pair(node,cost));
        }
    for(i=1;i<=n;i++)
        drum[i]=INF;
    drum[1]=0;
    q.push(1);
    cnt[1]=1;
    viz[1]=true;
    BellmanFord();
    if(cicle)
        fout<<"Ciclu negativ!"<<endl;
    else
        for(i=2;i<=n;i++)
            fout<<drum[i]<<" ";
    return 0;
}