#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
#define N_MAX 50002
#define INFINIT (1 << 30) - 1
using namespace std;

const int START = 1;

int n, m;
int cost[N_MAX];
int counter[N_MAX];
vector< pair<int, int> > liste[N_MAX]; // first = cost
                                       // second = nod
queue< pair<int, int> > q;

inline void citire ();
inline bool BellmanFord ();

int main()
{
    citire();

    for (int i = 1; i <= n; ++i) cost[i] = INFINIT;

    if (BellmanFord()) {
        printf("Ciclu negativ!\n");
    } else {
        for (int i = 2; i <= n; ++i) {
            printf("%d ", cost[i]);
        }
        printf("\n");
    }

    return 0;
}

inline void citire() {
    freopen("bellmanford.in", "r", stdin);
    freopen("bellmanford.out", "w", stdout);

    scanf("%d%d", &n, &m);

    int x, y, c;

    for (int i = 1; i <= m; ++i) {
        scanf("%d%d%d", &x, &y, &c);
        liste[x].push_back(make_pair(c, y));
    }
}

inline bool BellmanFord() {
    q.push(make_pair(0, START));
    cost[START] = 0;
    counter[START]++;

    while (!q.empty()) {
        int nod = q.front().second;
        int c = q.front().first;
        int v_size = liste[nod].size();

        for (int i = 0; i < v_size; ++i) {
            int otherNod = liste[nod][i].second;
            int otherCost = liste[nod][i].first;

            if (c + otherCost < cost[otherNod]) {
                cost[otherNod] = c + otherCost;
                q.push(make_pair(cost[otherNod], otherNod));
                counter[otherNod]++;

                if (counter[otherNod] > n) return true; // a, depistat un ciclu de cost negativ
            }
        }
        q.pop();
    }
    return false;
}