#include <iostream>
#include <fstream>
#include <string>
#include <cstring>
#include <algorithm>
#include <utility>
#include <cmath>
#include <map>
#include <deque>
#include <vector>
#include <set>
#include <list>
#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], ok;
bitset<MAX_SIZE + 1> notGood;


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;
            notGood[nextPeak] = 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));
    }
    list<int> graphPeaks;
    graphPeaks.push_back(1);
    for (int i = 2; i <= peaks; ++i) {
        graphPeaks.push_back(i);
        costs[i] = INT_MAX;
    }
    for (int i = 1; i < peaks; ++i) {
        ok = 1;
        for (int i = 1; i <= peaks; ++i) {
            notGood[i] = 0;
        }
        for (int actPeak : graphPeaks) {
            if (costs[actPeak] != INT_MAX) {
                findMinCosts(actPeak);
            }
        }
        list<int>::iterator itr;
        for (itr = graphPeaks.begin(); itr != graphPeaks.end(); ++itr) {
            if (notGood[*itr] == 0) {
                graphPeaks.remove(*itr++);
            }
        }
        if (ok) {
            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] << " ";
        }
    }
}