#include <cstdio>
#include <vector>
#include <deque>
#define INF (1<<30)
#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);
    }

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

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

    while(!C.empty()){

        F[C.front()] = 0;

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

            int nod = V[C.front()][i+0];
            int cost= V[C.front()][i+1];

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

                D[nod] = D[C.front()] + cost;

                if(F[nod] == 0){

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

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

        C.pop_front();

    }

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

    return 0;
}