#include <iostream>
#include <fstream>
#include <limits.h>
#define NLIM 50001
#define MLIM 250001

using namespace std;
ifstream f("bellmanford.in");
ofstream g("bellmanford.out");

int n, m, dis[NLIM];
struct Muchie {
    int s, d, c;
}Muhcii[MLIM];

bool BellmanFord(int start) {
    dis[start] = 0;

    for(int i=1; i<=n-1; i++) {
        for(int j=1; j<=m; j++) {
            int u = Muhcii[j].s;
            int v = Muhcii[j].d;
            int c = Muhcii[j].c;

            if(dis[u] != INT_MAX && dis[u]+c < dis[v]) {
                dis[v] = dis[u]+c;
            }
        }
    }

    for(int i=1; i<=m; i++) {
        int u = Muhcii[i].s;
        int v = Muhcii[i].d;
        int c = Muhcii[i].c;
        if(dis[u] != INT_MAX && dis[u]+c < dis[v]) {
            return 1;
        }
    }

    return 0;
}

void citire() {
    f >> n >> m;
    for(int i=1; i<=n; i++)
        dis[i] = INT_MAX;
    for(int i=1; i<=m; i++)
        f >> Muhcii[i].s >> Muhcii[i].d >> Muhcii[i].c;
}
void afisare(bool state) {
    if(state)
        g << "Ciclu negativ!";
    else for (int i = 2; i <= n; ++i)
            if(dis[i] != INT_MAX)
                g << dis[i] << ' ';
    g << '\n';
}
int main() {
    citire();
    afisare(BellmanFord(1));
    return 0;
}