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

ifstream f("bellmanford.in");
ofstream g("bellmanford.out");

int n, m;
vector <pair <int, int>> * lv;

int * d;
bool negative_cycle = false;

void SPFC(int start_node){

    queue <int> q;

    bool * in_q = new bool [n + 1];
    int * cnt_relaxations = new int [n + 1];

    for(int i = 0; i <= n; i++){

        in_q[i] = false;
        cnt_relaxations[i] = 0;
    }

    q.push(start_node);
    d[start_node] = 0;
    in_q[start_node] = true;

    while(!q.empty()){

        int current_node = q.front();
        q.pop();
        in_q[current_node] = false;

        for(int i = 0; i < lv[current_node].size(); i++){

            int next_node = lv[current_node][i].first;
            int next_price = lv[current_node][i].second;

            if(d[current_node] + next_price < d[next_node]){

                d[next_node] = d[current_node] + next_price;

                if(!in_q[next_node]){

                    cnt_relaxations[next_node] ++;

                    q.push(next_node);
                    in_q[next_node] = true;

                    if(cnt_relaxations[next_node] > n){

                        negative_cycle = true;
                        return;
                    }
                }
            }
        }
    }
}

int main(){

    f >> n >> m;

    lv = new vector <pair <int, int>> [n + 1];
    d = new int [n + 1];

    for(int i = 0; i <= n; i++)
        d[i] = 1000000000;

    int x, y, c;
    for(int i = 0; i < m; i++){

        f >> x >> y >> c;

        lv[x].push_back(make_pair(y, c));
    }

    SPFC(1);

    if(negative_cycle == true){

        g << "Ciclu negativ!";
        return 0;
    }

    for(int i = 2; i <= n; i++){

        g << d[i] << " ";
    }

    return 0;
}