#include <iostream>
#include <vector>
#include <stdio.h>
#include <cstring>
using namespace std;

class Muchie {
public:
    int Vec;
    int Cost;
    int Passed;
    Muchie () {}
    Muchie (int v, int c) {
        Vec = v;
        Cost = c;
		Passed = 0;
    }
};

vector<Muchie> v[50001];
int Paths[50001];

int Chain1[250001];
int Chain1Level;
int Chain2[250001];
int Chain2Level;
bool ChooseChain; //Double Lord Helix Implementation

int sol[50000];
int main () {
    freopen("bellmanford.in", "r", stdin);
    freopen("bellmanford.out", "w", stdout);
    int Noduri, Muchii;
    scanf("%d%d", &Noduri, &Muchii);

    for (int i = 0; i < Muchii; i++) {
        int orig, dest, cost;
        scanf("%d%d%d", &orig, &dest, &cost);
        v[orig].push_back(Muchie(dest, cost));
    }

    memset(Paths, 'G', (Noduri + 1) * 4);
    Paths[1] = 0;
    Chain1Level = 0;
    Chain2Level = 0;
    for (int i = 0; i < v[1].size(); i++) {
        Chain1[Chain1Level++] = v[1][i].Vec;
        Paths[v[1][i].Vec] = v[1][i].Cost;
    }

    ChooseChain = false;
    while (true) {
        if (ChooseChain) {
            if (Chain2Level == 0)
                break;
            for (int i = 0; i < Chain2Level; i++) {
                int vecin = Chain2[i];
                for (int k = 0; k < v[vecin].size(); k++) {
                    if (Paths[v[vecin][k].Vec] > Paths[vecin] + v[vecin][k].Cost) {
                        if (Paths[v[vecin][k].Vec] > 1000000000)
                            Chain1[Chain1Level++] = v[vecin][k].Vec;

                        v[vecin][k].Passed++;
                        if (v[vecin][k].Passed == Noduri) {
                            cout <<"Ciclu negativ!";
                            return 0;
                        }
                        Paths[v[vecin][k].Vec] = Paths[vecin] + v[vecin][k].Cost;
                    }
                }
            }
            Chain2Level = 0;
        } else {
            if (Chain1Level == 0)
                break;
            for (int i = 0; i < Chain1Level; i++) {
                int vecin = Chain1[i];
                for (int k = 0; k < v[vecin].size(); k++) {
                    if (Paths[v[vecin][k].Vec] > Paths[vecin] + v[vecin][k].Cost) {
                        if (Paths[v[vecin][k].Vec] > 1000000000)
                            Chain2[Chain2Level++] = v[vecin][k].Vec;

                        v[vecin][k].Passed++;
                        if (v[vecin][k].Passed == Noduri) {
                            cout <<"Ciclu negativ!";
                            return 0;
                        }

                        Paths[v[vecin][k].Vec] = Paths[vecin] + v[vecin][k].Cost;
                    }
                }
            }
            Chain1Level = 0;
        }
        ChooseChain = !ChooseChain;
    }

    for (int destin = 2; destin <= Noduri; destin++) {
        if (Paths[destin] > 1000000000)
            printf("0 ");
        else
            printf("%d ", Paths[destin]);
    }
}