#include <bits/stdc++.h>

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

#define MAXN     50005
#define INF 1000000005

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> Queue;
bool InQueue[MAXN];
bool BellmanFord(int Source = 1) {
    for (int i=1; i<=N; ++i)
        Dist[i] = INF;
    Dist[Source] = 0;

    int Front;
    Queue.push(Source);
    while (!Queue.empty()) {
        Front = Queue.front();
        Queue.pop();

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

        for (auto Edge:ADC[Front])
            if (Dist[Edge.first] > Dist[Front] + Edge.second) {
                Dist[Edge.first] = Dist[Front] + Edge.second;
                if (!InQueue[Edge.first])
                     InQueue[Edge.first] = true, Queue.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;
}