#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];
bool in_queue[MAX_N];
int used[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> qu;

    int u, v, c;

    qu.push(1);

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

    dist[1] = 0;

    while (!qu.empty()) {
        u = qu.front();
        qu.pop();

        in_queue[u] = false;

        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;

                if (!in_queue[v]) {
                    if (used[v] > n) {
                        return -1;
                    }
                    qu.push(v);
                    in_queue[v] = true;
                    used[v] ++;
                }
            }
        }
    }

    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;
}