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

using namespace std;

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

const int NMAX = 50'001;
const int INF = (1LL << 31) - 1;

int N, M;
vector < pair < int, int > > G[NMAX];

pair < bool, vector < int > > bellmanFord(const int& src) {

    vector < int > dist(N + 1, INF);
    vector < int > inQueueCounter(N + 1, 0);
    vector < bool > inQueue(N + 1, false);
    queue < int > q;

    q.push(src);
    dist[src] = 0;
    inQueueCounter[src]++;
    inQueue[src] = true;

    while(!q.empty()) {

        const int node = q.front();
        inQueue[node] = false;
        q.pop();

        for(const pair < int, int >& neighbor : G[node]) {

            if(dist[node] + neighbor.second < dist[neighbor.first]) {

                dist[neighbor.first] = dist[node] + neighbor.second;

                if(!inQueue[neighbor.first]) {
                    q.push(neighbor.first);
                    inQueueCounter[neighbor.first]++;
                    inQueue[neighbor.first] = true;
                    if(inQueueCounter[neighbor.first] > N - 1)
                        return { true, {} };
                }
            }
        }
    }

    return { false, dist };
}

int main() {

    f >> N >> M;

    for(int i = 1;i <= M;++i) {
        int u, v, c;
        f >> u >> v >> c;

        G[u].push_back({ v, c });
    }

    auto sol = bellmanFord(1);

    if(sol.first)
        g << "Ciclu negativ!";
    else
        for(int node = 2;node <= N;++node)
            g << sol.second[node] << ' ';

    return 0;
}