#include <bits/stdc++.h>
using namespace std;

#ifdef LOCAL
ifstream in("in.in");
ofstream out("out.out");
#else
ifstream in("bellmanford.in");
ofstream out("bellmanford.out");
#endif

int n,m;
vector<vector<pair<int,int>>> g;

vector<int> dis;
const int inf = 1000000005;
bool bellmanford() {
    dis = vector<int>(n + 1, inf);
    priority_queue<pair<int,int>> q;
    q.push({0 , 1});
    dis[1] = 0;
    vector<int> viz(n + 1, 0);
    while(!q.empty()) {
        int node = q.top().second;
        int val = q.top().first;
        q.pop();

        viz[node]++;
        if (viz[node] > n) {
            return false;
        }
        
        if (dis[node] < val) continue;

        for (auto k : g[node]) {
            if (dis[k.first] > dis[node] + k.second) {
                dis[k.first] = dis[node] + k.second;
                q.push({dis[k.first] , k.first});
            }
        }
    }
    return true;
}
int main() {
    in >> n >> m;
    g.resize(n + 1);
    for (int i = 1; i <= m; i++) {
        int u,v,c;
        in >> u >> v >> c;
        g[u].push_back({v,c});
    }

    if (bellmanford()) {
        for (int i = 2; i <= n; i++) {
            out << dis[i] << " ";
        }
        out << "\n";
    } else {
        out << "Ciclu negativ!\n";
    }
}