#include <iostream>
#include <fstream>
#include <vector>
#include <set>
#include <queue>
using namespace std;

#define nmax 50001
#define inf (1<<30)
ifstream in("bellmanford.in");
ofstream out("bellmanford.out");

int n,m,a,b,x,i;
int cost[nmax],viz_nod[nmax];
vector < pair <int, int> > vecin[nmax];
set < pair <int , int> > S;

void bellmanford(){
    
    for (i=2; i<=n; i++) cost[i]=inf;
    
    S.insert(make_pair(0, 1));
    
    while (!S.empty()){
        int nod=(*S.begin()).second;
        int MIN=(*S.begin()).first;
        
        S.erase(S.begin());
        
        for (i=0; i<vecin[nod].size(); i++){
            int vc=vecin[nod][i].first;
            int c=vecin[nod][i].second;
            
            viz_nod[vc]++;
            
            if (viz_nod[vc]>n){
                out << "Ciclu negativ!";
                return;
            }
            
            if (cost[vc]>MIN+c){
                cost[vc]=MIN+c;
                S.insert(make_pair(cost[vc], vc));
            }
            
        }
        
    }
    
    for (i=2; i<=n; i++)
        out << cost[i] << " ";
    out << "\n";
    
}

int main(){
    
    in >> n >> m;
    
    for (i=1; i<=m; i++)
        in >> a >> b >> x,
        vecin[a].push_back(make_pair(b, x));
    
    bellmanford();
    
    return 0;
}