#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#define inf (1<<30)
#define nmax 50005
using namespace std;

struct graph_content{
    vector <pair <int, int> > content[nmax];
    int number_of_nodes;
    int number_of_edges;
    int shortest_path [nmax];
    int cycle[nmax];
    bool if_cycle;
};

graph_content read_graph (){
    graph_content graph;
    ifstream fin ("bellmanford.in");
    fin >> graph.number_of_nodes >> graph.number_of_edges;
    for (int i = 1; i <= graph.number_of_edges; i++){
        int node1, node2, distance;
        fin >> node1 >> node2 >> distance;
        graph.content[node1].push_back (make_pair (node2, distance));
    }
    for (int i = 1; i <= graph.number_of_nodes; i++){
        graph.cycle[i] = 0;
        graph.shortest_path[i] = inf;
    }
    graph.shortest_path[1] = 0;
    return graph;
}

bool bellman_ford (graph_content &graph){
    queue <int> que;
    que.push(1);
    while (!que.empty ()){
        int current_node = que.front ();
        int node_distance = graph.shortest_path[current_node];
        que.pop ();
        for (auto neigh : graph.content[current_node])
            if (graph.shortest_path[neigh.first] > node_distance + neigh.second){
                graph.shortest_path[neigh.first] = node_distance + neigh.second;
                que.push (neigh.first);
                graph.cycle[neigh.first] ++;
                if (graph.cycle[neigh.first] >= graph.number_of_nodes)
                    return false;
            }
    }
    return true;
}

void print_shortest_path (graph_content &graph){
    ofstream fout ("bellmanford.out");
    if (!graph.if_cycle)
        fout << "Ciclu negativ!";
    else
        for (int i = 2; i <= graph.number_of_nodes; i++)
            fout << graph.shortest_path[i] << " ";
}

int main(){
    graph_content graph;
    graph = read_graph();
    graph.if_cycle = bellman_ford (graph);
    print_shortest_path (graph);
    return 0;
}