#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <fstream>
#include <queue>
#include <climits>
using namespace std;

const int NMAX = 50000;
const int MMAX = 250000;
int N, M;

vector<pair<int, int>> adj[NMAX + 1];
vector<int> dist;

struct Edge {
    int x, y;
    int cost;
} E[MMAX + 1];

void readInput() {
    ifstream f("bellmanford.in");

    f >> N >> M;
    for (int i = 1; i <= M; i++) {
        f >> E[i].x >> E[i].y >> E[i].cost;
    }
    dist = vector<int>(N + 1, INT_MAX);
    f.close();
}

int bellmanFord() {
    dist[1] = 0;

    for (int i = 1; i <= N; i++){
        for (auto edge : E) {
            if (dist[E[i].x] + E[i].cost < dist[E[i].y]) {
                if (i == N){
                    return 1;
                }

                dist[E[i].y] = dist[E[i].x] + E[i].cost;
            }
        }
    }

    return 0;
}

void output(string msj) {
    ofstream g("bellmanford.out");

    if (msj != "")
        g << msj;
    else
        for (int i = 2; i <= N; i++) {
            g << dist[i] << " ";
        }

    g.close();
}

int main() {
    readInput();

    string msj = "";
    if (bellmanFord() == 1)
        msj = "Ciclu negativ!";

    output(msj);
    return 0;
}