#include <iostream>
#include <vector>
#include <queue>
#include <limits.h>

#include <fstream>

using namespace std;

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

#define N 100000

struct Node {
    int idx;
    int weight;
};

bool inQueue[N];

// this vector is used to counter how many times a node was
// inserted in queue
int inQueue_cnt[N];

int dist[N];

int n, m;
vector<Node> adj_list[N];

void init_dist(int max_node) {
    for (int i = 1; i <= max_node; i++)
        dist[i] = INT_MAX;
}

void init_inqueue(int max_node) {
    for (int i = 1; i <= max_node; i++) {
        inQueue[i] = false;
        inQueue_cnt[i] = 0;
    }
}

int BellManFord(int start_node) {

    init_dist(n);
    init_inqueue(n);
    
    dist[start_node] = 0;

    queue<int> q;
    q.push(start_node);
    inQueue[start_node] = true;

    while (!q.empty()) {

        int node = q.front();
        q.pop();
        inQueue[node] = false;

        for (auto adj_node : adj_list[node]) {

            if (dist[adj_node.idx] != INT_MAX
		&& dist[adj_node.idx] > dist[node] + adj_node.weight) {
                dist[adj_node.idx] = dist[node] + adj_node.weight;

                if (!inQueue[adj_node.idx]) {

                    if (inQueue_cnt[adj_node.idx] > n) {
                        return -1;
                    } else {
                        q.push(adj_node.idx);
                        inQueue[adj_node.idx] = true;
                        inQueue_cnt[adj_node.idx]++;
                    }
                }
            }
        }
    }

    return 0;
}

int main() {

    int s, x, y, c;

    in >> n >> m;

    s = 1;

    // scanf("%d %d %d", &n, &m, &s);

    for (int i = 1; i <= m; i++) {
        in >> x >> y >> c;
        // scanf("%d %d %d", &x, &y, &c);
        adj_list[x].push_back({y, c});
    }

    int err = BellManFord(s);
    if (err == -1) {
        out << "Ciclu negativ!";
        // printf("Graph has negative-weight cycles\n");
        return 0;
    }

    for (int i = 2; i <= n; i++) {
        if (dist[i] != INT_MAX) {
            out << dist[i] << " ";
            // printf("%d ", dist[i]);
        } else { 
            out << "0 ";
            //printf("NaN ");
        }
    }
    printf("\n");

    return 0;
}