#include <cstdio>
#include <vector>
#define INF (1<<30)
#define DIM 51000
using namespace std;

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

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);
    }

    K = 1;
    C[1] = 1;
    F[1] = 1;

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

    for(int k = 1; k <= K; k ++){

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

        F[C[k]] = 0;

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

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

            if(D[nod] > D[C[k]] + cost){

                D[nod] = D[C[k]] + cost;

                if(F[nod] == 0){

                    Nr[nod] ++;
                    F[nod] = 1;
                    C[++K] = nod;

                }
            }
        }
    }

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

    return 0;
}