#include <cstdio>
#include <vector>
#include <deque>
#define INF ((1LL<<31)-1)
#define DIM 51000
using namespace std;

int N, M, K, X, Y, Z;
int D[DIM], F[DIM], Nr[DIM];
vector <int> V[DIM];
deque <int> C;

int main(){

    freopen("bellmanford.in" ,"r", stdin );
    freopen("bellmanford.out","w", stdout);

    scanf("%d %d", &N, &M);

    for(int i = 1; i <= M; i ++){

        scanf("%d %d %d", &X, &Y, &Z);

        V[X].push_back(Y);
        V[X].push_back(Z);
    }

    C.push_back(1);
    F[1] = 1;
    Nr[1] = 1;

    for(int i = 2; i <= N; i ++)
        D[i] = INF;

    while(!C.empty()){
        
        int nod = C.front();

        for(int i = 0; i < V[nod].size(); i += 2){

            int vec = V[nod][i+0];
            int cost= V[nod][i+1];

            if(D[vec] > D[nod] + cost){

                D[vec] = D[nod] + cost;

                if(F[vec] == 0){

                    Nr[vec] ++;
                    F[vec] = 1;
                    C.push_back(vec);

                    if(Nr[vec] == N){
                       
                       printf("Ciclu negativ!");
                       return 0;
                     }
                }
            }
        }

        F[nod] = 0;
        C.pop_front();

    }

    for(int i = 2; i <= N; i ++)
        printf("%d ", D[i]);

    return 0;
}