#include <iostream>
#include <fstream>
#include <string>
#include <cstring>
#include <algorithm>
#include <utility>
#include <cmath>
#include <map>
#include <deque>
#include <vector>
#include <set>
#include <queue>
#include <bitset>
#include <limits.h>
using namespace std;

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

const int MAX_SIZE = 50000;

vector<pair<int, int>> graph[MAX_SIZE + 1];
int costs[MAX_SIZE + 1];
int ok;

void findMinCosts(int actPeak) {
    for (pair<int, int> next : graph[actPeak]) {
        int nextPeak = next.first;
        int archCost = next.second;
        if (costs[actPeak] + archCost < costs[nextPeak]) {
            costs[nextPeak] = costs[actPeak] + archCost;
            ok = 0;
        }
    }
}

int main() {
    int peaks, arches;
    fin >> peaks >> arches;
    for (int i = 1; i <= arches; ++i) {
        int start, end, cost;
        fin >> start >> end >> cost;
        graph[start].push_back(make_pair(end, cost));
    }
    for (int i = 2; i <= peaks; ++i) {
        costs[i] = INT_MAX;
    }
    for (int i = 1; i < peaks; ++i) {
        ok = 1;
        for (int actPeak = 1; actPeak <= peaks; ++actPeak) {
            if (costs[actPeak] != INT_MAX) {
                findMinCosts(actPeak);
            }
        }
        if (ok == 1) {
            break;
        }
    }
    ok = 1;
    for (int actPeak = 1; actPeak <= peaks; ++actPeak) {
        if (costs[actPeak] != INT_MAX) {
            findMinCosts(actPeak);
        }
    }
    if (!ok) {
        fout << "Ciclu negativ!";
    } else {
        for (int i = 2; i <= peaks; ++i) {
            fout << costs[i] << "\n";
        }
    }
}

/*

 
 
 
 
 */