#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};
    vizitat[start] ++;
    dist[start] = 0;
    for(int i = 1; i <= n; ++ i) {
        if(i != start) {
            dist[i] = (1 << 30);
        }
    }
    for(int k = 1; k <= n - 1; ++ k) {
        for(int nod = 1; nod <= n; ++ nod) {
            if(dist[nod] != (1 << 30)) {
                for(auto vecin: g[nod]) {
                    int new_dist = dist[nod] + vecin.second;
                    if(new_dist < dist[vecin.first]) {
                        dist[vecin.first] = new_dist;
                    }
                }
            }
        }
    }

    for(int nod = 1; nod <= n; ++ nod) {
        for(auto vecin: g[nod]) {
            int new_dist = dist[nod] + vecin.second;
            if(new_dist < dist[vecin.first])
                return false;
        }
    }

    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;
}