#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];
bitset<MAX_SIZE + 1> isInQueue;
int costs[MAX_SIZE + 1], modifiedPrice[MAX_SIZE + 1];

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;
    }
    queue<int> positions;
    positions.push(1);
    int isNegative = 0;
    while (!isNegative && !positions.empty()) {
        int actPeak = positions.front();
        positions.pop();
        isInQueue[actPeak] = 0;
        for (pair<int, int> next : graph[actPeak]) {
            int nextPeak = next.first;
            int archCost = next.second;
            if (modifiedPrice[nextPeak] >= peaks) {
                isNegative = 1;
                break;
            }
            if (costs[actPeak] + archCost < costs[nextPeak] && !isInQueue[nextPeak]) {
                costs[nextPeak] = costs[actPeak] + archCost;
                isInQueue[nextPeak] = 1;
                positions.push(nextPeak);
                ++modifiedPrice[nextPeak];
            }
        }
    }
    if (isNegative) {
        fout << "Ciclu negativ!";
    } else {
        for (int i = 2; i <= peaks; ++i) {
            fout << costs[i] << " ";
        }
    }
}