#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#define nmax 50001
#define node first
#define weight second
#define inf (1<<30)
using namespace std;

void get_data (int &n_nodes, int &n_edges, int dist[nmax], vector <pair <int, int> > edges[nmax]){
    ifstream fin ("bellmanford.in");
    fin >> n_nodes >> n_edges;
    for (int i = 2; i <= n_nodes; i++)
        dist[i] = inf;
    for (int i = 1; i <= n_edges; i++){
        int node_1, node_2, weight;
        fin >> node_1 >> node_2 >> weight;
        edges[node_1].push_back (make_pair (node_2, weight));
    }
}

bool bellmanford (int n_nodes, int dist[nmax], vector <pair <int, int> > edges[nmax]){
    queue <int> q;
    int cycle[nmax];
    for (int i = 1; i <= n_nodes; i++)
        cycle[i] = 0;
    q.push(1);
    while (!q.empty ()){
        int current_node = q.front ();
        q.pop ();
        cycle [current_node] ++;
        if (cycle[current_node] == n_nodes - 1)
            return true;
        for (auto neigh : edges[current_node])
            if (dist[neigh.node] > dist[current_node] + neigh.weight){
                q.push (neigh.node);
                dist[neigh.node] = dist[current_node] + neigh.weight;
            }
    }
}

void print_data (bool cycle, int n_nodes, int dist[nmax]){
    ofstream fout ("bellmanford.out");
    if (!cycle)
        for (int i = 2; i <= n_nodes; i++)
            fout << dist[i] << " ";
    else
        fout << "Ciclu negativ!";
}

int main(){
    int n_nodes, n_edges;
    int dist[nmax];
    bool cycle = false;
    vector <pair <int, int> > edges[nmax];
    get_data (n_nodes, n_edges, dist, edges);
    cycle = bellmanford (n_nodes, dist, edges);
    print_data (cycle, n_nodes, dist);
    return 0;
}