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

#define NMAX 50050
#define MMAX 2500001
#define INF 999999999
using namespace std;



int n, m;

vector<pair<int, int>> graph[NMAX];

int dist[MMAX];
int vizited[NMAX];


bool bellmanFord(){
    for(int i = 2; i <= n; i++){
        dist[i] = INF;
    }
    dist[1] = 0;


    queue<int> q;


    q.push(1);
    while(!q.empty()){
        int current = q.front();
        vizited[current]++;
        if(vizited[current] >= m){
            return false;
        }
        q.pop();
        for(int i = 0; i < graph[current].size(); i++){
                pair<int, int> x = graph[current][i];
            if(dist[x.first] > dist[current] + x.second){
                dist[x.first] = dist[current] + x.second;
                q.push(x.first);
            }

        }
    }

    return true;

}


int main(){
    ifstream be("bellmanford.in");
    ofstream ki("bellmanford.out");

    be >> n >> m;
    int from, to, cost;
    for(int i = 0; i < m; i++){
        be >> from >> to >> cost;

        graph[from].push_back({to, cost});

    }

    bool ok = bellmanFord();


    if(!ok){
        ki << "Ciclu negativ!";
    }
    else{
        for(int i = 2; i <= n; i++){
            ki << dist[i] << " ";
        }
    }


}