#include <bits/stdc++.h>

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#define ll long long
#define ld long double

using namespace std;
using namespace __gnu_pbds;

typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

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

const int NMAX = 5e4;
const int INF = 1e9;

int n, m;
int d[NMAX + 1];
int relaxed[NMAX + 1];
bool in_q[NMAX + 1];
vector<pair<int, int>> g[NMAX + 1];
queue<int> q;

int main() {
    ios::sync_with_stdio(0);
    fin.tie(0);
    fout.tie(0);

    fin >> n >> m;
    for(int i = 1; i <= m; i++) {
        int a, b, c;
        fin >> a >> b >> c;
        g[a].emplace_back(b, c);
    } 

    for(int i = 1; i <= n; i++) {
        d[i] = INF;
    }

    q.push(1);
    d[1] = 0;
    relaxed[1] = 1;
    in_q[1] = 1;
    while(!q.empty()) {
        int node = q.front();
        q.pop();
        in_q[node] = 0;

        for(auto [next_node, edge_c] : g[node]) {
            if(d[node] + edge_c < d[next_node]) {
                d[next_node] = d[node] + edge_c;
                if(!in_q[next_node]) {
                    q.push(next_node);
                    in_q[next_node] = 1;
                    relaxed[next_node]++;
                    if(relaxed[next_node] == n) {
                        fout << "Ciclu negativ!";
                        return 0;
                    }
                }
            }
        }
    }

    for(int i = 2; i <= n; i++) {
        fout << d[i] << ' ';
    }
    fout << '\n';

    return 0;
}