#include <stdio.h>
#include <vector>
#include <set>
#include <algorithm>
#include <fstream>
using namespace std;
ifstream in("bellmanford.in");
ofstream out("bellmanford.out");

#define NMAX 50005
#define INF 200000200

struct Muchii{
    int x, y, c;
};

Muchii Muchie[250005]; ///muchiile grafului;
int N, M;
int D[NMAX],///D[x] = dist minima de la sursa la x
f[NMAX]; ///f[x] = 1 / 0 daca nodul x e / nu este in Heap
vector <pair<int, int> > Heap;
vector <int> Graf[NMAX];

void afis(int a[NMAX]) {
    for(int i = 1; i <= N; i++)
        out<<a[i]<<' ';
    out<<'\n';
}

void init() {
    int i;
    D[1] = 0;
    for(i = 2; i <= N; i++) D[i] = INF;
    Heap.push_back(make_pair(0, 1)); ///d[1], 1(nodul);
    make_heap(Heap.begin(), Heap.end());
}

void bellman_ford() {
    pair <int, int> Block;
    int i, nod, poz;
    long long pas = 0;
    while(Heap.size() && pas <= 1LL*N*M) {
        pas++;
        pop_heap(Heap.begin(), Heap.end()); ///alegem muchia de cost minim -> nodul din care porneste aceasta
        Block = Heap.back();
        Heap.pop_back();
        nod = Block.second; f[nod] = 0; ///nodul nod nu se mai gaseste in heap (deoarece a fost extras)
        for(i = 0; i < Graf[nod].size(); i++) {
            poz = Graf[nod][i]; ///poz = muchia care pleaca din: nod
            if(D[nod] + Muchie[poz].c < D[Muchie[poz].y]) {
                D[Muchie[poz].y] = D[nod] + Muchie[poz].c;
                if(!f[Muchie[poz].y]) { ///daca celalalt capat al muchiei nuse afla in Heap
                    f[Muchie[poz].y] = 1;
                    Heap.push_back(make_pair(D[Muchie[poz].y], Muchie[poz].y));
                    push_heap(Heap.begin(), Heap.end());
                }
            }
        }
    }
}

bool check_negative() {
    int i;
    for(i = 1; i <= M; i++)
        if(D[Muchie[i].x] + Muchie[i].c < D[Muchie[i].y])
            return true;
    return false;
}

int main()
{
    int i;

    in>>N>>M;
    for(i = 1; i <= M; i++) {
        in>>Muchie[i].x>>Muchie[i].y>>Muchie[i].c;
        Graf[Muchie[i].x].push_back(i);
    }

    init();
    bellman_ford();

    if(check_negative())
        out<<"Ciclu negativ!\n";
    else
        for(i = 2; i <= N; i++)
            out<<D[i]<<' ';

    return 0;
}