#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <climits>
#define mesaj "Ciclu negativ!"

using namespace std;

int n, m;
vector<pair<int, int>> list[50005];
int counter[50005];
bool inQueue[50005];
queue<int> q;
int d[50005];

bool bellmanford(){
    q.push(0);
    while(!q.empty()){
        int x = q.front();
        q.pop();
        inQueue[x] = false;
        for(auto it : list[x]){
            if(d[x] + it.second < d[it.first])
                d[it.first] = d[x] + it.second;
            if(!inQueue[it.first]){
                q.push(it.first);
                inQueue[it.first] = true;
            }
            counter[it.first]++;
            if(counter[it.first] >= n)
                return false;
        }
    }
    return true;
}

int main() {
    ifstream f("bellmanford.in");
    ofstream g("bellmanford.out");
    f>>n>>m;
    for (int i = 0; i < m; ++i) {
        int x, y, z;
        f>>x>>y>>z;
        list[x - 1].emplace_back(y - 1, z);
    }
    d[0] = 0;
    for (int i = 1; i < n; ++i) {
        d[i] = INT_MAX;
    }
    if(bellmanford()) g<<mesaj;
    else{
        for (int i = 1; i < n; ++i) {
            g<<d[i]<<' ';
        }
    }
    return 0;
}