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

using namespace std;

using bFordType = pair < bool, vector < int > >;

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

const int NMAX = 50001;
const int INF = (1 << 30);

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

bFordType ford(int src) {

    vector < int > dist(N + 1, INF);
    vector < int > counter(N + 1, 0);
    queue < int > q;

    dist[src] = 0;
    counter[src]++;

    for(q.push(src);!q.empty();) {

        const int node = q.front();

        q.pop();
        inQueue[node] = 0;

        for(auto& neighbor : G[node]) {

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

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

                if(!inQueue[neighbor.first]) {

                    inQueue[neighbor.first] = 1;
                    q.push(neighbor.first);
                    counter[neighbor.first]++;

                    if(counter[neighbor.first] > N - 1)
                        return { true, {} };
                }
            }
        }
    }

    return { false, dist };
}

int main() {

    f >> N >> M;

    for(;M--;) {

        int u, v, c;
        f >> u >> v >> c;

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

    auto sol = ford(1);

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

    return 0;
}