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

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

const int INF = 0x3F3F3F3F;
const int MAXN = 50001;

vector<pair<int,int>> G[MAXN];
int d[MAXN], viz[MAXN], n;

void BellmanFord(int nodeStart) {
    queue<int> q;
    q.push(nodeStart);
    viz[nodeStart] = 1;
    d[nodeStart] = 0;

    while(!q.empty()) {
        int node = q.front();
        q.pop();

        for(auto nxt : G[node])
            if(d[node] + nxt.second < d[nxt.first]) {
                d[nxt.first] = d[node] + nxt.second;
                q.push(nxt.first);
                viz[nxt.first]++;
                if(viz[nxt.first] > n) {
                    fout << "Ciclu negativ!\n";
                    return;
                }
            }
    }

    for(int i = 2; i <= n; i++)
        fout << (d[i] == INF ? -1 : d[i]) << " ";
    fout << "\n";
}

int main() {
    int m, x, y, c;

    fin >> n >> m;
    while(m--) {
        fin >> x >> y >> c;
        G[x].emplace_back(y, c);
    }

    for(int i = 2; i <= n; i++)
        d[i] = INF;

    BellmanFord(1);

    return 0;
}