#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#define nmax 50005
#define node first
#define inf (1<<30)
#define weight second
using namespace std;

vector <pair<int, int> > v[nmax];
queue <int> q;
int dist[nmax], prev[nmax], ciclu[nmax];

void get_data(int &n){
   int m, x, y, w;
   ifstream fin ("bellmanford.in");
   fin >> n >> m;
   for(int i= 1; i<= m; i++){
        fin >> x >> y >> w;
        v[x].push_back(make_pair(y, w));
   }
   for(int i= 2; i<= n; i++)    dist[i]= inf;
}

void print_data(int n){
    for(int i= 1; i<=n; i++){
        cout << i << "-> ";
        for(auto x: v[i])
            cout << x.first << " " << x.second << " ";
        cout << "\n";
    }
}

void bellman_ford(int n){
    ofstream fout ("bellmanford.out");
    q.push(1);
    while(!q.empty()){
        int cur= q.front();
        q.pop();
        ciclu[cur]++;
        if(ciclu[cur]> n-1){
            fout << "Ciclu negativ!";
            return;
        }
        for(auto x: v[cur]){
            if(dist[x.node]> dist[cur] + x.weight){
                dist[x.node]= dist[cur]+ x.weight;
                q.push(x.node);
            }
        }
    }
    for(int i= 2; i<= n; i++)   fout << dist[i] << " ";
}

int main(){
    int n;
    get_data(n);
    bellman_ford(n);
    return 0;
}