#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#define nmax 50005
#define inf (1<<30)
using namespace std;

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

int n, m;
int cost[nmax], used[nmax];
vector < pair<int, int> > v[nmax];
queue < pair<int, int> > Q;

void readData() {
    int i, a, b, c;
    fin >> n >> m;
    for (i = 1; i <= m; i++) {
        fin >> a >> b >> c;
        v[a].push_back(make_pair(b, c));
    }
    for (i = 2; i <= n; i++)
        cost[i] = inf;
}

void solve() {
    int i;
    // nod, cost
    Q.push(make_pair(1, 0));
    while (!Q.empty()) {
        int nod = Q.front().first;
        int costCurent = Q.front().second;
        Q.pop();
        for (i = 0; i < v[nod].size(); i++) {
            int vecinCurent = v[nod][i].first;
            int vecinCost = v[nod][i].second;
            
            if (costCurent + vecinCost < cost[vecinCurent]){
                cost[vecinCurent] = costCurent + vecinCost;
                Q.push(make_pair(vecinCurent, cost[vecinCurent]));
                used[vecinCurent]++;
                if (used[vecinCurent] >= n) {
                    fout << "Ciclu negativ!\n";
                    return;
                }
            }
        }
    }
    for (i = 2; i <= n; i++)
        fout << cost[i] << " ";
    fout << "\n";
}

int main() {
    readData();
    solve();
    fin.close();
    fout.close();
    return 0;
}