#include <bits/stdc++.h>

using namespace std;
int const inf = (1 << 30) , NM = 5e4 + 7;
struct code{
    int to , cost;
};
vector <code> v [NM];
int dp [NM] , mark [NM] , n , m;
bool is = 1;
inline void Bford (){
    int i , j;
    queue <int> Q;
    Q . push (1);
    while (! Q . empty ()){
        int curent = Q . front ();
        ++ mark [curent];
        if (mark [curent] >= n){
            is = 0;
            return;
        }
        else{
            vector <code> :: iterator i;
            for(i = v [curent] . begin () ; i != v [curent] . end () ; ++ i){
                if (i -> cost + dp [curent] < dp [i -> to]){
                    dp [i -> to] = i -> cost + dp [curent];
                    Q . push (i -> to);
                }
            }
        }
        Q . pop ();
    }
}
int main()
{
    FILE *Cin , *Cout;
    Cin = fopen ("bellmanford.in" , "r");
    Cout = fopen ("bellmanford.out" , "w");
    fscanf (Cin , "%d %d" , &n , &m);
    for(int i = 1 ; i <= m ; ++ i){
        int a , b , c;
        fscanf (Cin , "%d %d %d" , &a , &b , &c);
        v [a] . push_back ({b , c});
    }
    fill (dp + 2 , dp + n + 1 , inf);
    Bford ();
    if (is)
        for(int i = 2 ; i <= n ; ++ i)
            fprintf (Cout , "%d " , dp [i]);
    else
        fputs ("Ciclu negativ!" , Cout);
    return 0;
}