#include <bits/stdc++.h>

using namespace std;

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


vector<pair<int, int>> g[50003];
int n, m;

void citire() {
    in >> n >> m;

    for(int i = 1; i <= m; ++ i) {
        int x, y, z;
        in >> x >> y >> z;
        g[x].push_back(make_pair(y, z));
    }
}

bool bf(int start) {
    int dist[50003];
    int vizitat[50003] = {0};
    dist[start] = 0;
    for(int i = 1; i <= n; ++ i) {
        if(i != start) {
            dist[i] = (1 << 30);
        }
    }

    queue<int> coada;
    bool esteincoada[50003] = {0};
    coada.push(start);
    esteincoada[start] = 1;
    while(!coada.empty()) {
        int nod_cur = coada.front();
        vizitat[nod_cur] ++;
        coada.pop();
        esteincoada[nod_cur] = 0;

        if(vizitat[nod_cur] >= n)
            return false;

        for(auto vecin: g[nod_cur]) {
            int new_dist = dist[nod_cur] + vecin.second;

            if(new_dist < dist[vecin.first]) {
                dist[vecin.first] = new_dist;
                coada.push(vecin.first);
            }
        }

    }

    for(int i = 1; i <= n; ++ i) {
            if(i != start) {
                out << dist[i] << " ";
        }
    }

    return true;
}

int main() {
    citire();
    if(!bf(1)) {
        out << "Ciclu negativ!";

    }
    return 0;
}