#include <bits/stdc++.h>

#define int_pair std::pair <int, int>

#define MAXN     50005
#define INF 2000000005

int N, M;
std::vector <int_pair> ADC[MAXN];

inline void AddEdge(int X, int Y, int W) {
    ADC[X].push_back({Y, W});
}

int Dist[MAXN], Times[MAXN];
std::queue <int> Q;
bool BellmanFord(int Start = 1) {
    for (int i=1; i<=N; ++i)
        Dist[i] = INF;
    Dist[Start] = 0;
    Q.push(Start);

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

        Times[Front] ++;
        if (Times[Front] == N) return false;

        for (auto Edge:ADC[Front])
            if (Dist[Edge.first] > Edge.second + Dist[Front])
                Dist[Edge.first] = Edge.second + Dist[Front],
                Q.push(Edge.first);
    }   return true;
}

std::ifstream In ("bellmanford.in");
std::ofstream Out("bellmanford.out");

void Citire() {
    In >> N >> M;
    for (int i=1, X, Y, W; i<=M; ++i)
        In >> X >> Y >> W, AddEdge(X, Y, W);
}

void Rezolvare() {
    if (BellmanFord()) {
        for (int i=2; i<=N; ++i, Out << ' ')
            Out << Dist[i];
    }
    else
        Out << "Ciclu negativ!\n";
}

int main()
{
    Citire();
    Rezolvare();

    return 0;
}