#include <bits/stdc++.h>
#define pb push_back
using namespace std;
ifstream f("bellmanford.in");
ofstream g("bellmanford.out");
typedef long long ll;
typedef pair<int, int> pi;
int t, T;

void Bellman(int n, int source, vector<vector<pi>>& edges) {
    vector<int> d(n + 1, INT_MAX), R(n + 1, 0);
    vector<bool> is_there(n + 1, false);
    queue<int> qu;
    qu.push(source);
    is_there[source] = true;
    d[source] = 0;

    while (!qu.empty()) {
        int node = qu.front();
        qu.pop();
        is_there[node] = false;
        R[node]++;

        if (R[node] >= n) {
            g << "Ciclu negativ!";
            return;
        }

        for (pi& el : edges[node]) {
            int neigh = el.first;
            int weight = el.second;
            if (d[neigh] > d[node] + weight) {
                d[neigh] = d[node] + weight;
                if (!is_there[neigh]) {
                    is_there[neigh] = true;
                    qu.push(neigh);
                }
            }
        }
    }

    for (int i = 2; i <= n; i++)
        if (d[i] == INT_MAX) g << 0 << ' ';
        else g << d[i] << ' ';
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, m;
    f >> n >> m;

    vector<vector<pi>> V(n + 1);
    for (int i = 0; i < m; i++) {
        int a, b, c;
        f >> a >> b >> c;
        V[a].push_back({ b, c });
    }

    Bellman(n, 1, V);


    return 0;
}