#include <bits/stdc++.h>

using namespace std;

const int MAXN = 50010;
long long DP[MAXN];
struct Edge{
    long long from, to, dist;
};
vector<pair<int,int> > V[MAXN];
int N, M;
int CNT[MAXN];

int main() {

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

    fin >> N >> M;
    for (int i = 1; i <= M;i++) {
        int from, to , dist;
        fin >> from >> to >> dist;
        V[from].push_back({to, dist});

    }

    for (int i = 1; i <= N;i++) DP[i] = 1e9;
    DP[1] = 0;
    queue<int> Q;
    Q.push(1);
    while(!Q.empty()) {
        int current= Q.front();
        Q.pop();
        if (CNT[current] > N) {
            cout << "Ciclu negativ!";
            return 0;
        }
        CNT[current]++;
        for (auto edge: V[current]) {
            if (DP[current] + edge.second < DP[edge.first]) {
                DP[edge.first] = DP[current] + edge.second;
                Q.push(edge.first);
            }
        }
    }

    for (int i = 2; i <= N;i++) cout << DP[i] << " ";
    return 0;
}