#include <bits/stdc++.h>
using namespace std;


//void* getMinimumDistances(int numberOfNodes, const vector<vector<int>> &adjacencyList, int sourceNode) {
//    int distanceTo[numberOfNodes];
//    set<int> modifiedNodes;
//
//    for (int i=0; i<numberOfNodes; i++) {
//        distanceTo[i]=INT_MAX;
//    }
//
//    distanceTo[sourceNode] = 0;
//    modifiedNodes.insert(sourceNode);
//
//    while()
//}



//void* getMinimumDistances(int numberOfNodes, const vector<vector<pair<int, int>>> &adjacencyList, int sourceNode, int *distanceTo) {
//    set<int> modifiedNodes;
//    int timesUpdated[numberOfNodes];
//
//    for (int i=0; i<numberOfNodes; i++) {
//        distanceTo[i]=INT_MAX;
//        timesUpdated[i]=0;
//    }
//
//    distanceTo[sourceNode] = 0;
//    timesUpdated[sourceNode] = 1;
//    modifiedNodes.insert(sourceNode);
//
//    int currentNode, iteration=0;
//    while(not modifiedNodes.empty()) {// and iteration++ < numberOfNodes) {
//        currentNode = *modifiedNodes.begin();
//        modifiedNodes.erase(currentNode);
//
//        for (const auto &adjacentNode : adjacencyList[currentNode])
//            if (distanceTo[currentNode] + adjacentNode.second < distanceTo[adjacentNode.first]) {
//                if (timesUpdated[adjacentNode.first] > numberOfNodes - 1)
//                    return nullptr;
//
//                distanceTo[adjacentNode.first] = distanceTo[currentNode] + adjacentNode.second;
//                timesUpdated[adjacentNode.first]++;
//                modifiedNodes.insert(adjacentNode.first);
//            }
//    }
//
//    return (void *)distanceTo;
//}


void* getMinimumDistances(int numberOfNodes, const vector<vector<pair<int, int>>> &adjacencyList, int sourceNode, int *distanceTo) {
    queue<int> modifiedNodes;
    int timesUpdated[numberOfNodes];

    for (int i=0; i<numberOfNodes; i++) {
        distanceTo[i]=INT_MAX;
        timesUpdated[i]=0;
    }

    distanceTo[sourceNode] = 0;
    timesUpdated[sourceNode] = 1;
    modifiedNodes.push(sourceNode);

    int currentNode, iteration=0;
    while(not modifiedNodes.empty()) {// and iteration++ < numberOfNodes) {
        currentNode = modifiedNodes.front();
        modifiedNodes.pop();

        for (const auto &adjacentNode : adjacencyList[currentNode])
            if (distanceTo[currentNode] + adjacentNode.second < distanceTo[adjacentNode.first]) {
                if (timesUpdated[adjacentNode.first] > numberOfNodes - 1)
                    return nullptr;

                distanceTo[adjacentNode.first] = distanceTo[currentNode] + adjacentNode.second;
                timesUpdated[adjacentNode.first]++;
                modifiedNodes.push(adjacentNode.first);
            }
    }

    return (void *)distanceTo;
}


int main() {
    int numberOfNodes, numberOfEdges, firstNode, secondNode, cost;

    ifstream input("bellmanford.in");

    input>>numberOfNodes>>numberOfEdges;
    vector<vector<pair<int, int>>> adjacencyList(numberOfNodes, vector<pair<int, int>>());

    for (int i=0; i<numberOfEdges; i++) {
        input>>firstNode>>secondNode>>cost;
        firstNode--; secondNode--;
        adjacencyList[firstNode].push_back({secondNode, cost});
    }

    input.close();

    ofstream output("bellmanford.out");

    int distanceTo[numberOfNodes];

    if (getMinimumDistances(numberOfNodes, adjacencyList, 0, distanceTo) == nullptr)
        output<<"Ciclu negativ!";
    else
        for (int i=1; i<numberOfNodes; i++)
            output<<distanceTo[i]<<' ';

    output.close();

    return 0;
}