#include <fstream>
#include <vector>

using namespace std;

ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");

void Bellman_Ford(int source, int noNodes, vector<vector<int> > &edges) {

    vector<int> distances(noNodes+1, 1e9);
    distances[source] = 0;

    for(int i=1; i<= noNodes-1; i++) {

        for(auto edge : edges) {
            int firstNode = edge[0];
            int secondNode = edge[1];
            int weight = edge[2];

            if(distances[firstNode] + weight < distances[secondNode])
                distances[secondNode] = distances[firstNode] + weight;
        }
    }

    for(auto edge : edges) {
        int firstNode = edge[0];
        int secondNode = edge[1];
        int weight = edge[2];

        if(distances[firstNode] + weight < distances[secondNode]) {
            fout << "Ciclu negativ!";
            return;
        }
    }

    for(int i=2; i<=noNodes; i++)
        fout << distances[i] << ' ';

}

int main() {

    int noNodes, noEdges;
    fin >> noNodes >> noEdges;

    vector<vector<int> > edges;

    for(int i=1; i<=noEdges; i++) {
        int firstNode, secondNode, weight;
        fin >> firstNode >> secondNode >> weight;
        edges.push_back({firstNode, secondNode, weight});
    }

    Bellman_Ford(1, noNodes, edges);


    return 0;
}