#include <cstdio>
#include <cstring>
#include <cassert>

#include <fstream>
#include <algorithm>
#include <vector>
#include <string>
#include <queue>
#include <map>

#define v first
#define c second

using namespace std;

typedef long long LL;
typedef pair<int, int> Edge;
typedef vector<Edge>::iterator it;

const int oo = 0x3f3f3f3f;
const int MAX_N = 50005;

vector<Edge> G[MAX_N];
int N, Distance[MAX_N], TimesRelaxed[MAX_N];
queue<int> Q;
bool InQ[MAX_N], NegativeCycle;

void InitBellmanFord(int Source) {
    memset(Distance, oo, sizeof(Distance));
    Distance[Source] = 0;
    Q.push(Source); InQ[Source] = true;
}

inline bool Relax(int X, int Y, int C) {
    if (Distance[X] + C < Distance[Y]) {
        Distance[Y] = Distance[X] + C;
        return true;
    }
    return false;
}

void BellmanFord(int Source) {
    for (InitBellmanFord(Source); !Q.empty(); Q.pop()) {
        int X = Q.front(); InQ[X] = false;
        for (it Y = G[X].begin(); Y != G[X].end(); ++Y) {
            if (Relax(X, Y->v, Y->c) && !InQ[Y->v]) {
                ++TimesRelaxed[Y->v];
                if (TimesRelaxed[Y->v] >= N) {
                    NegativeCycle = true;
                    return;
                }
                Q.push(Y->v); InQ[Y->v] = true;
            }
        }
    }
}

void Solve() {
    BellmanFord(1);
}

void Read() {
    assert(freopen("bellmanford.in", "r", stdin));
    int M; assert(scanf("%d %d", &N, &M) == 2);
    for (; M > 0; --M) {
        int X, Y, C; assert(scanf("%d %d %d", &X, &Y, &C) == 3);
        G[X].push_back(Edge(Y, C));
    }
}

void Print() {
    assert(freopen("bellmanford.out", "w", stdout));
    if (NegativeCycle) {
        printf("Ciclu negativ!\n");
        return;
    }
    for (int X = 2; X <= N; ++X) {
        if (Distance[X] == oo)
            Distance[X] = 0;
        printf("%d ", Distance[X]);
    }
    printf("\n");
}

int main() {
    Read();
    Solve();
    Print();
    return 0;
}