#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <queue>
#include <string>
#define Nmax 50000
#define inf 0x3f3f3f3f
using namespace std;

int main() {
    ifstream f("bellmanford.in");
    ofstream g("bellmanford.out");

    int n, m, v, d, s, p, source;
    string line;
    vector < pair< int, int > > graf[Nmax];
    int used[Nmax], c[Nmax];
    queue<int> q;

    f >> n >> m;

    for (int i = 0; i < m; ++i) {
        f >> d >> s >> p;
        graf[--d].push_back({ --s, p });
    }
    source = 0;
  
    for (int i = 0; i < n; ++i) {
        c[i] = inf;
        used[i] = 0;
    }

    c[source] = 0;
    used[source] = 1;
    q.push(source);
    while (!q.empty()) {
        int node = q.front();
        cout << node << ' ';
        q.pop();
        for (int j = 0; j < graf[node].size(); ++j) {
            int node2 = graf[node][j].first;
            int cost = graf[node][j].second;
            if (c[node2] > c[node] + cost) {
                if (used[node2] == n) {
                    g << "Ciclu negativ!\n";
                    return 0;
                }
                c[node2] = c[node] + cost;
                used[node2]++;
                q.push(node2);
            }
        }
    }

    for (int i = 1; i < n; ++i) {
        g << c[i] << ' ';
    }
}