#include <fstream>
#include <vector>
using namespace std;

///(cost, (sursa, destinatie))
vector <pair <int, pair <int, int> > > edges;
///function performs bellmanford on graph
///returns false if the graph has a negative weight cycle
///return true otherwise
///in the vector dist, we find the distances from source to all other nodes of the graph
bool bellmanford(int source, int numberOfNodes, int numberOfEdges, vector <int> &dist) {
    dist.resize(numberOfNodes, INT_MAX);
    dist[source] = 0;
    for(int i = 1; i <= numberOfNodes - 1; ++i) {
        for(int j = 0; j < numberOfEdges; ++j) {
            int src = edges[j].second.first;
            int dest = edges[j].second.second;
            int cost = edges[j].first;
            ///dist[src] != INT_MAX, means that node src has been visited
            if(dist[src] != INT_MAX && dist[src] + cost < dist[dest]) {
                dist[dest] = dist[src] + cost;
            }
        }
    }

    ///if after numberOfNodes - 1 iterations we find a shorter path to any node
    ///it means that we have a negative weight cycle
    for(int j = 0; j < numberOfEdges; ++j) {
        int src = edges[j].second.first;
        int dest = edges[j].second.second;
        int cost = edges[j].first;
        if(dist[src] != INT_MAX && dist[src] +cost < dist[dest]){
            return false;
        }
    }

    return true;

}

int main()
{
    ifstream f("bellmanford.in");
    ofstream g("bellmanford.out");
    int n, m;
    f >> n >> m;
    for(int i = 0; i < m; ++i) {
        int src, dest, cost;
        f >> src >> dest >> cost;
        edges.push_back(make_pair(cost, make_pair(src, dest)));
    }
    vector <int> dist;
    if(bellmanford(1, n, m, dist)) {
        for(int i = 2; i <= n; ++i) {
            g << dist[i] << " ";
        }
    } else {
        g << "Ciclu negativ!";
    }
    f.close();
    g.close();
    return 0;
}