#include <bits/stdc++.h>

#define NMAX 50000
#define INFINIT 300000000

using namespace std;

ifstream fin ("bellmanford.in");
ofstream fout ("bellmanford.out");

int dist[NMAX + 1];
vector< pair<int, int> >G[NMAX + 1];

int main()
{
    int N, M;
    fin >> N >> M;

    for(int i = 1; i <= M; i++){
        int a, b, c;
        fin >> a >> b >> c;
        G[a].push_back({b, c});
    }

    for(int i = 1; i <= N; i++){
        dist[i] = INFINIT;
    }
    dist[1] = 0;
    bool MADE_CHANGES = true;
    int iterations = 1;
    while(iterations <= N + 1 && MADE_CHANGES){
        MADE_CHANGES = false;

        for(int node = 1; node <= N; node++){
            for(int i = 0; i < G[node].size(); i++){
                int vec = G[node][i].first;
                int cost = G[node][i].second;

                if(dist[node] + cost < dist[vec]){
                    dist[vec] = dist[node] + cost;
                    MADE_CHANGES = true;
                }
            }
        }

        iterations++;
    }

    if(iterations == N + 2 && MADE_CHANGES == true){
        fout << "Ciclu negativ!";
        return 0;
    }

    for(int i = 2; i <= N; i++){
        fout << dist[i] << ' ';
    }
    fout << "\n";

    return 0;
}