#include <bits/stdc++.h>

#define MAXN 50005
#define inf  (int)(1e9)
#define int_pair std::pair <int, int>
#define mp       std::make_pair

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

inline void AddEdge(int x, int y, int w) {
    ADC[x].push_back({y, w});
}

bool InQueue[MAXN];
int Dist[MAXN], Times[MAXN];

#define Vecin Edge.first

std::queue <int> Queue;
void BellmanFord(int Source = 1) {
    for (int i=1; i<=N; ++i)
        Dist[i] = inf;
    Dist[Source] = 0;

    Queue.push(1);
    InQueue[1] = 0;

    int Front;
    while (!Queue.empty() && !Cycle) {
        Front = Queue.front();
        Queue.pop();

        InQueue[Front] = 0;
        for (auto Edge:ADC[Front])
            if (Dist[Vecin] > Dist[Front] + Edge.second) {
                Dist[Vecin] = Dist[Front] + Edge.second;

                if (!InQueue[Vecin]) {
                    if (Times[Vecin] > N)
                        Cycle = 1;
                    else
                        ++ Times[Vecin],
                        InQueue[Vecin] = 1,
                        Queue.push(Vecin);
                }
            }
    }
}

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

void Citire() {
    In >> N >> M;
    for (int i=0, x, y, w; i<M; ++i)
        In >> x >> y >> w, AddEdge(x, y, w);
}

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

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

    return 0;
}