#include <fstream>
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");
int n, m;
const int INF = ((1<<31)-1), N = 50002;
vector<pair<int, int> >V[N];
void bellmanFord(int start){
    queue<int> Q;
    int dist[N] = {0}, checked[N] = {0};
    for(int i=2; i<=n; i++)
        dist[i] = INF;
    Q.push(1);

    while(!Q.empty()){
        int nod = Q.front();
        Q.pop();
        for(auto it : V[nod]){
            if(dist[it.first] > dist[nod] + it.second){
                dist[it.first] = dist[nod] + it.second;
                Q.push(it.first);
                cout << it.first <<  ' ';
                checked[it.first] ++;
                if(checked[it.first] == n){
                    fout << "Ciclu negativ";
                    return;
                }
            }
        }
    }
    for(int i=2; i<=n; i++){
        fout << dist[i] << ' ';
    }
}
int main()
{
    fin >> n >> m;
    for(int i=0; i<m; i++){//muchii
        int x1, x2, cost;
        fin >> x1 >> x2 >> cost;
        V[x1].push_back({x2, cost});
    }
    bellmanFord(1);
    return 0;
}