#include <bits/stdc++.h>

using namespace std;

const int maxn = 50010;
const int inf = 2e9;
vector< pair<int, int> > gr[maxn];
int vizitari[maxn];
bool viz[maxn];
int dist[maxn];
queue<int> bf;

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

int main(){
    int n, m;
    f >> n >> m;
    for(int i = 0; i < m; ++i){
        int a, b, c;
        f >> a >> b >> c;
        gr[a].push_back({b, c});
    }
    for(int i = 2; i <= n; ++i){
        dist[i] =  inf;
    }
    vizitari[1] = 1;
    bf.push(1);
    viz[1] = 1;
    while(bf.size()){
        int node = bf.front();
        if(vizitari[node] > n){
            g << "Ciclu negativ!";
            return 0;
        }

        viz[node] = 0;
        bf.pop();
        for(auto x : gr[node]){
            if(dist[x.first] > dist[node] + x.second){
                vizitari[x.first] ++;
                dist[x.first] = dist[node] + x.second;
                if(viz[x.first] == 0){
                    bf.push(x.first);
                    viz[x.first] = true;
                }
            }
        }
    }

    for(int i = 2; i <= n; ++i){
        g << dist[i] << ' ';
    }
    return 0;
}