#include <iostream>
#include <vector>
#include <queue>
#include <climits>

const int MAXN = 50005;
const int INF = INT_MAX;

int n, m;
std::vector<std::pair<int, int>> adj[MAXN];
int dist[MAXN];
bool inQueue[MAXN];
int count[MAXN];

bool bellmanFord() {

    for (int i = 1; i <= n; i++) {
        dist[i] = INF;
        inQueue[i] = false;
        count[i] = 0;
    }

    dist[1] = 0;
    std::queue<int> q;
    q.push(1);
    inQueue[1] = true;
    count[1] = 1;

    while (!q.empty()) {
        int u = q.front();
        q.pop();
        inQueue[u] = false;

        for (auto &edge : adj[u]) {
            int v = edge.first;
            int cost = edge.second;

            if (dist[u] != INF && dist[u] + cost < dist[v]) {
                dist[v] = dist[u] + cost;

                if (!inQueue[v]) {
                    q.push(v);
                    inQueue[v] = true;
                    count[v]++;

                    if (count[v] > n) {
                        return false;
                    }
                }
            }
        }
    }

    return true;
}
int main()
{
    freopen("bellmanford.in", "r", stdin);
    freopen("bellmanford.out", "w", stdout);

    std::cin >> n >> m;

    for (int i = 0; i < m; i++) {
        int x, y, c;
        std::cin >> x >> y >> c;
        adj[x].push_back({y, c});
    }

    if (!bellmanFord()) {
        std::cout << "Ciclu negativ!" << '\n';
    } else {
        for (int i = 2; i <= n; i++) {
            std::cout << dist[i];
            if (i < n) std::cout << " ";
        }
        std::cout << '\n';
    }

}