#include<stdio.h>
typedef unsigned short ushort;

int N, M, D[50001];
int E[250000][3];

int main()
{
    FILE *in = fopen("bellmanford.in", "r");
    FILE *out = fopen("bellmanford.out", "w");
    int i, j, ok, a, b, c;

    fscanf(in, "%d %d", &N, &M);
    for(i = 0; i < M; ++i)
	fscanf(in, "%d %d %d", &E[i][0], &E[i][1], &E[i][2]);

    for(i = 1; i <= N; ++i)
	D[i] = 1 << 29;
    D[1] = 0;

    for(ok = 1, i = 1; i < N && ok; ++i)
	for(ok = 0, j = 0; j < M; ++j)
	{
	    a = E[j][0];
	    b = E[j][1];
	    c = E[j][2];
	    if(D[a] + c < D[b])
	    {
		ok = 1;
		D[b] = D[a] + c;
	    }
	}

    if(ok)
    {
	for(i = ok = 0; i < M; ++i)
	    if(D[ E[i][0] ] + E[i][2] < D[ E[i][1] ])
		ok = 1;
	if(ok)
	    fprintf(out, "Ciclu negativ!\n");
    }

    if(!ok)
    {
	for(i = 2; i <= N; ++i)
		fprintf(out, "%d ", D[i]);
	fprintf(out, "\n");
    }

    fclose(in);
    fclose(out);
    return 0;
}