#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 visit_number[MAX_NODES + 1];
int sel[MAX_NODES + 1];

int negative_cycle;

int bellmanford(int num_nodes) {
    std::queue<int> q;
    int u, v, c;
    
    for (int i = 2; i <= num_nodes; i++) {
        dist[i] = INF;
    }
    
    sel[1] = 1;
    q.push(1);
    
    while (!q.empty() && !negative_cycle) {
        u = q.front();
        q.pop();
        sel[u] = 0;
        
        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;
                    if (!sel[v]) {
                        if (visit_number[v] > num_nodes) {
                            negative_cycle = 1;
                        } else {
                            q.push(v);
                            sel[v] = 1;
                            visit_number[v]++;
                        }
                    }
                }
            }
    }
    
 //  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));
    }
    
    bellmanford(n);
    
    if (negative_cycle == 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);
}