#include <bits/stdc++.h>
//#include <cstring>
//#include <string>
//#include <algorithm>
//#include <conio.h>
//#include <windows.h>

using namespace std;
string file1 = "date.in";
string file2 = "ascii.in";

ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");

int graph[5005][5005], n, m, dist[5005], previous[5005];

void citire() {
    int x, y, z;
    fin >> n >> m;
    for (int i = 1; i <= m; i++) {
        fin >> x >> y >> z;
        graph[x][y] = z;
    }
}

void graphic(ifstream &inputFile, string fileName) {
    string content;
//    inputFile.open(fileName);
    while (getline(inputFile, content)) {
        cout << content << endl;
        cout << content.size();
    }
    cout << endl << endl;
    inputFile.close();
}

bool bellmanFord(int start) {
    for (int i = 1; i <= n; i++) {
        dist[i] = 100000000;
        previous[i] = 0;
    }
    dist[start] = 0;
    for (int nod = 1; nod < n; nod++) {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (graph[i][j] != 0 && dist[j] > dist[i] + graph[i][j]) {
                    dist[j] = dist[i] + graph[i][j];
                    previous[j] = i;
                }
            }
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (graph[i][j] != 0 && dist[j] > dist[i] + graph[i][j]) {
                fout << "Ciclu negativ!";
                return false;
            }
        }
    }
    return true;
}

int main() {
    citire();
    if (bellmanFord(1))
        for (int i = 2; i <= n; i ++)
            fout << dist[i] << ' ';
    return 0;
}