#include <bits/stdc++.h>
#define Intro ios::sync_with_stdio(0), cin.tie(0)
#define ll long long
using namespace std;
ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");
int const N = 5e4 + 4;
vector<pair<int, int>> neighbours[N];
vector<int> costs(N, INT_MAX);
bitset<N> visited;

void find_costs() {
    queue<int> nodes;
    nodes.push(1);
    while (!nodes.empty()) {
        int node = nodes.front();
        nodes.pop();
        for (auto itr : neighbours[node]) {
            int neighbour = itr.first, curr_cost = itr.second;
            if (!visited[neighbour] or costs[neighbour] > costs[node] + curr_cost) {
                visited[neighbour] = true;
                costs[neighbour] = costs[node] + curr_cost;
                nodes.push(neighbour);
            }
        }
    }
}

int main() {
    int nodes, edges;
    fin >> nodes >> edges;
    for (int i = 1; i <= edges; ++i) {
        int src, dest, cost;
        fin >> src >> dest >> cost;
        neighbours[src].push_back({dest, cost});
    }
    costs[1] = 0;
    visited[1] = true;
    find_costs();
    if (costs[1] < 0) {
        fout << "Ciclu negativ!";
    } else {
        for (int i = 2; i <= nodes; ++i) {
            fout << costs[i] << ' ';
        }
    }
    return 0;
}