#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
#include <climits>

using namespace std;

#define INF INT_MAX
#define maxN 50005

vector <pair <int, int> > muchii[maxN];
queue <int> Q;
int cost[maxN], nodeCount[maxN];

int main()
{
    freopen("bellmanford.in", "r", stdin);
    freopen("bellmanford.out", "w", stdout);

    int N, M, x, y, c;

    scanf("%d %d", &N, &M);

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

    for(int i = 2; i <= N; ++i)
        cost[i] = INF;

    Q.push(1);

    while(!Q.empty()) {
        int root = Q.front();
        Q.pop();

        for(unsigned int i = 0; i < muchii[root].size(); ++i) {
            int node = muchii[root][i].first;
            int currCost = muchii[root][i].second;

            if(cost[root] + currCost >= cost[node])
                continue;

            cost[node] = cost[root] + currCost;
            Q.push(node);
            nodeCount[node]++;

            if(nodeCount[node] >= N) {
                printf("Ciclu negativ!");
                return 0;
            }
        }
    }

    for(int i = 2; i <= N; ++i)
        if(cost[i] == INF)
            printf("0 ");
        else printf("%d ", cost[i]);

    return 0;
}