#include <bits/stdc++.h>
 
#define NMAX 50010
#define oo (1 << 30)
 
using namespace std;
 

class Task {
 public:
    void solve() {
        read_input();
        get_result();
    }
 
 private:
    int n, m;
    int source;
    vector<pair<int, int>> adj[NMAX];
    queue<int> q;
    vector<int> dist;
 
    void read_input() {
        ifstream in("bellmanford.in");
        in >> n >> m;
        dist.resize(n + 1);

        source = 1;

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

        in.close();
    }
 
    void get_result() {
        if (BellmanFord(source, dist)) {
            ofstream out("bellmanford.out");
            out << "Ciclu negativ!";
            out.close();
        } else {
            print_output();
        }
    }
 
    bool BellmanFord(int source, vector<int> &d) {
        vector<int> used(n + 1, 0);

        for (int i = 1; i <= n; ++i) {
          dist[i] = oo;
        }

        dist[source] = 0;

        q.push(source);

        while (!q.empty()) {
            int node = q.front();
            q.pop();

            ++used[node];
            if (used[node] == n) {
                return true;
            }

            for (auto &edge : adj[node]) {
                int neighbour = edge.first;
                int cost_edge = edge.second;

                if (dist[node] + cost_edge < dist[neighbour]) {
                    dist[neighbour] = dist[node] + cost_edge;
                    q.push(neighbour);
                }
            }
        }

        return false;
    }

    void print_output() {
        ofstream out("bellmanford.out");

        for (int i = 1; i <= n; ++i) {
            if (i == source) {
                continue;
            }

            if (dist[i] == 0) {
                out << 0 << " ";
                continue;
            }

            out << dist[i] << " ";
        }
        out << "\n";

        out.close();
    }
};
 

int main() {
    Task *task = new Task();
    task->solve();
    delete task;
    return 0;
}