#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <limits.h>
#include <queue>

using namespace std;

typedef struct edge{
    int node;
    int weight;
} EDGE;

vector<EDGE> adjacencyList[50001];

long long costs[50001];
int foundNr[50001];

int n,m;

int bf(int startNode){
    queue<int> q;

    q.push(startNode);
    costs[startNode] = 0;

    while (!q.empty()){
        int currentNode = q.front();
        q.pop();

        for (int i=0; i<adjacencyList[currentNode].size(); i++){
            EDGE nextNodeEdge = adjacencyList[currentNode][i];

            //relax edge currentNode->nextNode
            if (costs[nextNodeEdge.node] > costs[currentNode] + nextNodeEdge.weight){
                costs[nextNodeEdge.node] = costs[currentNode] + nextNodeEdge.weight;
                foundNr[nextNodeEdge.node]++;
                q.push(nextNodeEdge.node);

                if (foundNr[nextNodeEdge.node] > n){
                    return 0;
                }
            }

        }
    }

    return 1;
}

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

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

    int from, to, cost;
    for (int i=0; i<m; i++){
        scanf("%d %d %d", &from, &to, &cost);
        EDGE e;
        e.node = to;
        e.weight = cost;

        adjacencyList[from].push_back(e);
    }

    for (int i=1; i<=n; i++){
        costs[i] = LONG_LONG_MAX;
    }

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

    return 0;
}