#include <fstream>
#include <queue>
#include <vector>
using namespace std;

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

queue<int> Q;
vector<vector<pair<int, int>>> vecini;
vector<int> visited;
vector<int> cost;

int main() {
    int n, m;
    fin >> n >> m;
    vecini.resize(n + 1);
    visited.reserve(n + 1);
    cost.reserve(n + 1);
    int a, b, w;
    while(m--) {
        fin >> a >> b >> w;
        vecini[a].push_back(make_pair(b, w));
    }
    Q.push(1);
    visited[1] = 1;
    cost[1] = 0;
    bool broken = false;
    while(!Q.empty() && !broken) {
        int x = Q.front();
        Q.pop();
        for(auto k : vecini[x]) {
            if (visited[k.first] == 0 || cost[k.first] > cost[x] + k.second) {
                if(visited[k.first] >= n) {
                    broken = true;
                    break;
                }
                visited[k.first]++;
                cost[k.first] = cost[x] + k.second;
                Q.push(k.first);
            }
        }
    }
    if(broken) {
        fout << "Ciclu negativ!";
    } else {
        for(int i = 2; i <= n; i++)
            fout << cost[i] << ' ';
    }
    return 0;
}