#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 Bell(int n, vector<vector<pair<int, int>>>& V) {
    vector<int> dp(n, INT_MAX), R(n, 0);
    vector<int> is_there(n, 0);

    queue<int> qu;
    qu.push(0);
    is_there[0] = 1;
    dp[0] = 0;

    while (!qu.empty()) {
        int nod = qu.front();
        qu.pop();
        is_there[nod] = 0;

        R[nod]++;

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

        for (const pair<int,int>& el : V[nod]) {
            int neigh = el.first;
            int cost = el.second;

            if (dp[neigh] > dp[nod] + cost) {
                dp[neigh] = dp[nod] + cost;
                if (is_there[neigh] == 0) {
                    is_there[neigh] = 1;
                    qu.push(neigh);
                }
            }
        }
    }

    for (int i = 1; i < n; i++) g << dp[i] << ' ';
}

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

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

    Bell(n, V);

    return 0;
}