#include <stdio.h>
#include <string.h>
#include <vector>
#include <queue>

#define MAX_NODES 50000
#define INF 999999999

std::vector<std::pair<int, int> > adj_list[MAX_NODES + 1];
int dist[MAX_NODES + 1];
int parent[MAX_NODES + 1];

int bellmanford(int num_nodes) {
    std::queue<int> q;
    int u, v, c;
    
    for (int i = 2; i <= num_nodes; i++) {
        dist[i] = INF;
    }
    
    for (auto &adj_node : adj_list[1]) {
        dist[adj_node.first] = adj_node.second;
        parent[adj_node.first] = 1;
        q.push(adj_node.first);
    }
    
    for (int i = 1; i < num_nodes - 1; i++) {
        for (int u = 1; u <= num_nodes; u++) {
            for (auto &adj_node : adj_list[u]) {
                v = adj_node.first;
                c = adj_node.second;
                if (dist[v] > dist[u] + c) {
                    dist[v] = dist[u] + c;
                    parent[v] = u;
                }
            }
        }
    }
    
    for (int u = 1; u <= num_nodes; u++) {
        for (auto &adj_node : adj_list[u]) {
            v = adj_node.first;
            c = adj_node.second;
            if (dist[v] > dist[u] + c) {
                return -1;
            }
        }
    }
    
    return 0;
    
}

int main(void) {
    FILE * fin = fopen("bellmanford.in", "r");
    FILE * fout = fopen("bellmanford.out", "w");
    
    int n, m, c, x, y;
    
    fscanf(fin, "%d%d", &n, &m);
    
    for (int i = 0; i < m; i++) {
        fscanf(fin, "%d%d%d", &x, &y, &c);
        adj_list[x].push_back(std::make_pair(y, c));
    }
    
    if (bellmanford(n) == 0) {
        for (int i = 2; i <= n; i++) {
            if (dist[i] < INF) {
                fprintf(fout, "%d ", dist[i]);
            } else {
                fprintf(fout, "0 ");
            }
        } 
    } else {
        fprintf(fout, "Ciclu negativ!");
    }
    
    fclose(fin);
    fclose(fout);
}