//
//  main.cpp
//  C++ - teste
//
//  Created by Filip Cuciuc on 03/02/2020.
//  Copyright © 2020 Filip Cuciuc. All rights reserved.
//

//#include <iostream>
#include <stdio.h>
#include <fstream>
#include <algorithm>
#include <vector>
#include <queue>
#include <math.h>
#include <map>
#include <string>
#include <cctype>
//#include "MED.h"
using namespace std;
//using namespace std::chrono;

ifstream cin("bellmanford.in");
ofstream cout("bellmanford.out");

const int MAX = 50010;
const int INF = 2000000;
int n, m;
int dist[MAX], counter[MAX];
bool updated[MAX];
vector< pair < int, int > > mat[MAX];
queue <int> q;


void read() {
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int A, B, C;
        cin >> A >> B >> C;
        mat[A].push_back({B, C});
    }
}


void solve() {
    read();
    
    for (int i = 2; i <= n; i++)
        dist[i] = INF;
    
    q.push(1);
    counter[1] = 1;
    while (!q.empty()) {
        int now = q.front();
        q.pop();
        updated[now] = 0;
        
        for (auto& x : mat[now]) {
            if (dist[x.first] > dist[now] + x.second) {
                dist[x.first] = dist[now] + x.second;
                q.push(x.first);
                
                updated[x.first] = 1;
                ++counter[x.first];
                //cout << counter[x.first] << endl;
                
                if (counter[x.first] == n) {
                    cout << "Ciclu negativ!";
                    return;
                }
            }
        }
    }
    for (int i = 2; i <= n; i++)
        cout << dist[i] << " ";
    

}

int main() {

    solve();

    return 0;
}