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

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



int n, m;

struct edge{
    int from, to, cost;


};

vector<edge> graph;

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


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


    queue<int> q;


    q.push(1);
    while(!q.empty()){
        int current = q.front();
        vizited[current]++;
        if(vizited[current] >= m){
            return false;
        }

        for(int i = 0; i < m; i++){
            int from = graph[i].from;
            int to = graph[i].to;
            int cost = graph[i].cost;
            if(dist[from] != INF && dist[from] + cost < dist[to]){
                dist[to] = dist[from] + cost;
                q.push(i);
            }

        }
        return true;


    }



}


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

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

        graph.push_back(w);

    }

    bool ok = bellmanFord();


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


}