#include <stdio.h>
#include <stdlib.h>
#define INFINIT 1000000000l

typedef struct
{
	int x, y, c;
} muchie;

int m, n;
int **la;
int **lc;
int *nr; //numar relaxari
int* d;

char* qc;

void citeste_graf()
{
	FILE* fi = fopen("bellmanford.in", "r");
	fscanf(fi, "%d%d", &n, &m);
	int i;
	int *nv = calloc(n + 1, sizeof(int));
	muchie *vm = malloc(m * sizeof(muchie));
	int x_curent, y_curent, cost_curent;
	for(i = 0; i < m; ++i)
	{
		fscanf(fi, "%d%d%d", &x_curent, &y_curent, &cost_curent);
		nv[x_curent]++;
		vm[i].x = x_curent;
		vm[i].y = y_curent;
		vm[i].c = cost_curent;
	}
	
	la = (int**)malloc((n + 1) * sizeof(int*));
	lc = (int**)malloc((n + 1) * sizeof(int*));
	
	for(i = 1; i <= n; ++i)
	{
		la[i] = (int*)malloc((nv[i] + 1) * sizeof(int));
		lc[i] = (int*)malloc((nv[i] + 1) * sizeof(int));
		la[i][0] = 0;
	}
	
	free(nv);
	
	for(i = 0; i < m; ++i)
	{
		x_curent = vm[i].x;
		y_curent = vm[i].y;
		cost_curent = vm[i].c;
		la[x_curent][0]++;
		la[x_curent][la[x_curent][0]] = y_curent;
		lc[x_curent][la[x_curent][0]] = cost_curent;
	}
	
	free(vm);
	
	nr = (int*)malloc((n + 1) * sizeof(int));
	for(i = 1; i <= n; ++i) nr[i] = m;
	
	qc = (char*)calloc(n + 1, sizeof(char));
	d = (int*)malloc((n + 1) * sizeof(int));
	for(i = 1; i <= n; ++i) d[i] = INFINIT;
	
	fclose(fi);
}

/* COADA */

#define QLEN 10000

int q[QLEN];
int qs = 0, qe = -1, qcnt = 0;

void inc_relax(int elem)
{
	nr[elem]--;
	if(!nr[elem]) 
	{
		FILE* fo = fopen("bellmanford.out", "w");
		fprintf(fo, "Ciclu negativ!\n");
		fclose(fo);
		exit(0);
	}
}

void qpush(int elem)
{
	if(qc[elem]) return;
	inc_relax(elem);
	qe++;
	if(qe == QLEN) qe = 0;
	qc[elem] = 1;
	q[qe] = elem;
	qcnt++;
}

int qpop()
{
	int r = q[qs];
	qs++;
	if(qs == QLEN) qs = 0;
	qc[r] = 0;
	qcnt--;
	return r;
}

/* BELLMAN FORD */

void bellman_ford()
{
	int e, v, i;
	qpush(1);
	d[1] = 0;
	while(qcnt)
	{
		e = qpop();
		for(i = 1; i <= la[e][0]; ++i)
		{
			v = la[e][i];
			if(d[v] > d[e] + lc[e][i])
			{
				d[v] = d[e] + lc[e][i];
				qpush(v);
			}
		}
	}
}

/* SCRIE REZULTAT */

void scrie_rezultat()
{
	FILE* fo = fopen("bellmanford.out", "w");
	int i;
	for(i = 2; i <= n; ++i) fprintf(fo, "%d ", d[i]);
	fprintf(fo, "\n");
	fclose(fo);
}

int main()
{
	citeste_graf();
	bellman_ford();
	scrie_rezultat();
	return 0;
}