#include <iostream>
#include <vector>
#include <queue>
#include <fstream>
using namespace std;
struct Muchii {
    int x, c;
}a;
const int NMAX = 55000, INF = 1 << 30;
int dist[NMAX + 5], viz[NMAX + 5], w[NMAX + 5];
int n, m, x, y, i;
bool ok = false;
vector <Muchii> g[NMAX + 5];
queue<int> q;
void Bellman_Ford();
int main() {
    ifstream cin("bellmanford.in");
    ofstream cout("bellmanford.out");
    cin >> n >> m;
    
    for(i = 1; i <= m; ++i) {
        cin >> x >> y >> w[i];
        a.x = y;
        a.c = w[i];
        g[x].push_back(a);
    }
    
    Bellman_Ford();
    if(ok == true) {
        cout << "Ciclu negativ!";
    } else {
        for(i = 2; i <= n; ++i)
            cout << dist[i] << " ";
    }
    cout << "\n";
    return 0;
}
void Bellman_Ford() {
    for(i = 1; i <= n; ++i) {
        dist[i] = INF;
    }
    dist[1] = 0;
    vector<Muchii>:: iterator it;
    
    q.push(1);
    while (!q.empty()) {
        int first = q.front();
        q.pop();
        viz[first]++;
        if(viz[first] == n) {
            ok = true;
            return;
        }
        for(it = g[first].begin(); it < g[first].end(); ++it) {
            a = *it;
            if(dist[a.x] > dist[first] + a.c) {
                dist[a.x] = dist[first] + a.c;
                q.push(a.x);
            }
            
        }
    }
    
}