#include "bits/stdc++.h"

using namespace std;

const int NMax = 50003;
const int INF = 1000000000;

int n,m,x,y,c;
int dist[NMax], been[NMax];
vector<pair<int,int> > G[NMax];
queue<int> q;

int main(){
    ifstream cin("bellmanford.in");
    ofstream cout("bellmanford.out");
    cin >> n >> m;
    for(int i = 0; i < m; ++i){
        cin >> x >> y >> c;
        G[x].push_back(make_pair(y,c)); 
    }
    for(int i = 1; i <= n; ++i){
        dist[i] = INF;
    }
    int start = 1;
    dist[start] = 0;
    q.push(1);
    while(!q.empty()){
        int nod = q.front();
        q.pop();
        for(int i = 0; i < G[nod].size(); ++i){
            if(dist[G[nod][i].first] > dist[nod] + G[nod][i].second){
                dist[G[nod][i].first] = dist[nod] + G[nod][i].second;
                q.push(G[nod][i].first);
                been[G[nod][i].first]++;
                if(been[G[nod][i].first] > n){
                    cout << "Ciclu negativ!" << '\n';
                    return 0;
                }
            }
        }
    }
    for(int i = 2; i <= n; ++i){
        cout << dist[i] << ' ';
    }
    cout << '\n';
    
    return 0;
}