#include <bits/stdc++.h>
#define ll long long
#define cin fin
#define cout fout
using namespace std;
ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");
int n, m, x, y, c;
ll minCost[500001];
vector <pair <int, int> > adj[500001];
tuple <int, int, int> edges[250005];


bool bellmanFord() {
    for (int i = 2; i <= n; i++)
        minCost[i] = 2e15;

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++) {
            int from, to, cost;
            tie(from, to, cost) = edges[j];

            minCost[to] = min(minCost[to], minCost[from] + cost);
        }

    for (int i = 1; i <= m; i++) {
        int from, to, cost;
        tie(from, to, cost) = edges[i];

        if (minCost[from] + cost < minCost[to])
            return 0;
    }
    return 1;
}

int main() {
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        cin >> get<0> (edges[i]) >> get<1> (edges[i]) >> get<2> (edges[i]);
        adj[x].push_back(make_pair(y, c));
    }

    if (!bellmanFord())
        cout << "Ciclu negativ!";
    else
        for (int i = 2; i <= n; i++)
            cout << minCost[i] << ' ';

    return 0;
}