#include <fstream>
#include <queue>
#include <vector>

using namespace std;

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

vector<int> distanta(50005, 1e9);
vector<bool> inQueue(50005, 0);
vector<int> relaxari(50005, 0);

bool Bellman_Ford(int source, int noNodes, vector<vector<pair<int,int> > > &graph) {

    queue<int> Q;
    
    Q.push(source);
    distanta[source] = 0;
    inQueue[source] = 1;

    while(!Q.empty()) {

        int node = Q.front();
        inQueue[node] = false;
        Q.pop();

        for(auto neighbor : graph[node]) {

            int weight = neighbor.first;
            int newNode = neighbor.second;

            if(distanta[node] + weight < distanta[newNode]) {
                distanta[newNode] = distanta[node] + weight;
                
                if(!inQueue[newNode]) {

                    Q.push(newNode);
                    inQueue[newNode] = true;
                    relaxari[newNode]++;

                    if(relaxari[newNode] > noNodes)
                        return false;
                }
            }
        }
    }

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

    return true;

}

int main() {

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

   vector<vector<pair<int,int> > > graph(noNodes+1, vector<pair<int,int> >());

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

        graph[firstNode].push_back({weight, secondNode});
    }

    if(Bellman_Ford(1, noNodes, graph) == 0)
        fout << "Ciclu negativ!";

    return 0;
}