#include <bits/stdc++.h>

using namespace std;

ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");
const int INF = 1e9 + 7;
struct Muchie {
    int vec, cost;
};
int n, m, i, j, cost[50002], fr[50002];
vector<Muchie> gr[50002];

static inline bool BellmanFord(int start = 1) {
    for(int i = 1; i <= n; i++) cost[i] = INF;

    queue<int> q;
    q.push(start);

    cost[start] = 0;
    while(!q.empty()) {
        int nod = q.front();
        q.pop();

        for(Muchie urm : gr[nod]) {
            if(cost[urm.vec] > cost[nod] + urm.cost) {
                cost[urm.vec] = cost[nod] + urm.cost;
                q.push(urm.vec);

                if(++fr[urm.vec] >= n) return false;
            }
        }
    }
    return true;
}

int main() {
    fin >> n >> m;
    for(i = 1; i <= m; i++) {
        int x, y, z;
        fin >> x >> y >> z;
        gr[x].push_back({y, z});
        //gr[y].push_back({x, z});
    }

    if(!BellmanFord()) fout << "Ciclu negativ!";
    else {
        for(i = 2; i <= n; i++) fout << cost[i] << " ";
    }

    return 0;
}