#include <iostream>
#include <fstream>
#include <vector>
#include <limits>
#include <list>

using namespace std;

ifstream in("bellmanford.in");
ofstream out("bellmanford.out");
int N, M;
vector<vector<pair<int,int>>> graph;
vector<int> dist;

void read() 
{
    int from, to, cost;

    in >> N >> M;

    graph.resize(N + 1);
    dist.resize(N + 1, numeric_limits<int>::max());

    for (int i = 0; i < M; i++) {
        in >> from >> to >> cost;
        graph[from].push_back(make_pair(to, cost));
    }
}

bool hasNegativeCycle(int start)
{
    list<int> q;
    vector<bool> visited(N + 1, false);
    vector<int> timesRelaxed(N + 1, 0);

    dist[start] = 0;
    timesRelaxed[start] = 1;
    q.push_back(start);

    while (!q.empty()) {
        int current = q.front();
        q.pop_front();
        visited[current] = false;

        for (int i = 0; i < graph[current].size(); i++) {
            int neighbour = graph[current][i].first;
            int edgecost = graph[current][i].second;

            if (dist[neighbour] > dist[current] + edgecost) {
                dist[neighbour] = dist[current] + edgecost;

                if (!visited[neighbour]) {
                    visited[neighbour] = true;
                    timesRelaxed[neighbour]++;
                    q.push_back(neighbour);
                }
            }
            if (timesRelaxed[neighbour] > N + 2) {
                return true;
            }
        }
    }

    return false;
}

int main()
{

    read();
    if (hasNegativeCycle(1)) {
        out << "Ciclu negativ!";
    }
    else {
        for (int i = 2; i <= N; i++) {
            out << dist[i] << " ";
        }
    }


    return 0;

}