#include <iostream>
#include <fstream>
#include <queue>
#include <vector>
#include <cmath>
#include <unordered_map>
using namespace std;
ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");

const int LMAX = 50005;
const int INF = 0x3F3F3F3F;
vector<pair<int, int>> L[LMAX];
priority_queue<pair<int, int>> Q;


int main() {
    int n, m;
    fin>>n>>m;
    int x, y, c;
    while (m--) {
        fin>>x>>y>>c;
        x--;
        y--;
        L[x].push_back({c, y});
    }
    vector<int> dist(n, INF), cnt(n, 0);
    dist[0] = 0;
    Q.push({0, 0});
    while (!Q.empty()) {
        int node = Q.top().second, d = -Q.top().first;
        Q.pop();
        if (d > dist[node]) continue;
        for (pair<int, int> vec : L[node]) {
            if (dist[vec.second] > dist[node] + vec.first) {
                dist[vec.second] = dist[node] + vec.first;
                    Q.push({-dist[vec.second], vec.second});
                    cnt[vec.second]++;
                    if (cnt[vec.second] > n - 1) {
                        fout<<"Ciclu negativ!";
                        return 0;
                    }
            }
        }
    }
    for (int i = 1; i < n; i++) {
        fout<<dist[i]<<" ";
    }




    fin.close();
    fout.close();
    return 0;
}