#include <iostream>
#include <fstream>
#include <vector>
#include <queue>

std::ifstream f("bellmanford.in");
std::ofstream g("bellmanford.out");

const int MAX_N = 50001;
const int MAX_INT = 2000000000;

std::vector<std::pair<int, int> > graph[MAX_N];
int dist[MAX_N];
int n, m;

void build_graph()
{
    int u, v, c;

    f >> n >> m;

    for (int i = 0; i < m; i ++) {
        f >> u >> v >> c;
        graph[u].push_back(std::pair<int, int> (v, c));
    }
}

int bellmanford()
{
    std::queue<int> qu1, qu2;

    int u, v, c;

    qu1.push(1);

    for (int i = 0; i <= n; i ++) {
        dist[i] = MAX_INT;
    }

    dist[1] = 0;

    for (int relax = 1; relax < n; relax ++) {
        while (!qu1.empty()) {
            u = qu1.front();
            qu1.pop();

            for (int i = 0; i < (int) graph[u].size(); i ++) {
                v = graph[u][i].first;
                c = graph[u][i].second;

                if (dist[v] > dist[u] + c) {
                    dist[v] = dist[u] + c;
                    qu2.push(v);
                }
            }
        }

        qu1 = qu2;
        qu2 = std::queue<int> ();
    }

    if (!qu1.empty()) {
        return -1;
    }

    return 0;
}

int main()
{
    build_graph();

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

    return 0;
}