#include <bits/stdc++.h>

#define INF 50000000

using namespace std;

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

vector <vector <pair <int, int>>> G;
vector <int> C;

int n, m;

void BellmanFord(int start) {
    C = vector <int> (n + 1, INF);
    vector <int> N0 (n + 1, 0);

    queue <int> Q;

    Q.push(start);
    N0[start] ++;
    C[start] = 0;

    while(!Q.empty()) {
        int Node = Q.front();
        Q.pop();

        for(auto x : G[Node]) {
            int Neighbour = x.first;
            int Cost = x.second;

            if(C[Neighbour] > C[Node] + Cost) {
                C[Neighbour] = C[Node] + Cost;
                
                Q.push(Neighbour);
                N0[Neighbour] ++;

                if(N0[Neighbour] == n) {
                    fout << "Ciclu negativ!\n";
                    exit(0);
                }

            }
        }
    }
}

int main() {
    fin >> n >> m;

    G.resize(n + 1);

    for(int i = 1; i <= m; i ++) {
        int x, y, c; fin >> x >> y >> c;
        G[x].push_back({y, c});
    }

    BellmanFord(1);

    for(int i = 2; i <= n; i ++)
        fout << C[i] << ' ';

    return 0;
}