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

#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[NMAX];


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

    for(int i = 1; i <= n - 1; i++){
        for(int j = 0; j < m; j++){
            int u = graph[j].from;
            int v = graph[j].to;
            int w = graph[j].cost;

            if(dist[u] != INF && dist[u] + w < dist[v])
                dist[v] = dist[u] + w;
        }
    }


    //verify that there are no negative cycles
    for(int i = 0; i < m; i++){
        int u = graph[i].from;
        int v = graph[i].to;
        int w = graph[i].cost;
        if(dist[u] != INF && dist[u] + w < dist[v])
            return false;
    }

    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] << " ";
        }
    }


}