/** fara cicluri negative */

#include <stdio.h>
#include <stdlib.h>

#define filein "bellmanford.in"
#define fileout	"bellmanford.out"
#define oo 2147000000

/* Coada */

typedef struct q_node {
	int key;
	struct q_node *next;
} Q_Node;

typedef struct queue {
	Q_Node *head, *tail;
	int size;
} *Q;

Q Q_New();
void Q_Delete(Q *q);
void Q_enqueue(Q q, int key);
int Q_dequeue(Q q);
int Q_empty(Q q);

Q Q_New()
{
	Q q = (Q) malloc ( sizeof(struct queue) );
	q->size = 0;
	q->head = q->tail = NULL;
	return q;
}

void Q_Delete(Q *q)
{
	while( !Q_empty(*q) )
		Q_dequeue(*q);
	free(*q);
}

void Q_enqueue(Q q, int key)
{
	Q_Node *new = (Q_Node*) malloc ( sizeof(Q_Node) );
	new->key = key;
	new->next = NULL;
	if(q->size == 0)
	{
		q->head = q->tail = new;
		q->size++;
		return;
	}
	q->size++;
	q->tail->next = new;
	q->tail = new;	
}

int Q_dequeue(Q q)
{
	int key = q->head->key;
	if( Q_empty(q) )
		return -1;
	Q_Node *old = q->head;
	q->size--;
	q->head = q->head->next;
	free(old);
	return key;
}

int Q_empty(Q q)
{
	return ( q->size == 0 );
}

int n, m;
int **la, **lc, *deg;

int* allocArray(int dim)
{
	int *a = (int*) calloc(dim, sizeof(int) );
	return a;
}

void pl()
{
	int i, j;
	for(i = 1; i <= n; i++)
	{
		printf("%d\n", i);
		for(j = 1; j < deg[i]; j++)
			printf("%d ", la[i][j]);
		printf("\n");
	}
}

void pa(int *a, int n)
{
	int i;
	for(i = 1; i <= n; i++)
		printf("%d ", a[i]);
	printf("\n");
}


void read()
{
	scanf("%d %d ", &n, &m);
	int i, x, y, cost;
	deg = allocArray(n+1);;
	la = (int**) malloc ( (n+1) * sizeof(int*) );
	lc = (int**) malloc ( (n+1) * sizeof(int*) );
	
	for(i = 1; i <= m; i++)
	{
		scanf("%d %d %d", &x, &y, &cost);
		deg[x]++;
	}
	fseek(stdin, 0, 0);
	scanf("%d %d ", &n, &m);
	for(i = 1; i <= n; deg[i++] = 1)
	{
		la[i] = allocArray(deg[i]+1); 
		lc[i] = allocArray(deg[i]+1); 
	}
	for(i = 1; i <= m; i++)
	{
		scanf("%d %d %d", &x, &y, &cost);
		la[x][ deg[x] ] = y;
		lc[x][deg[x]++] = cost; 
	}
}

void Bellman_Ford()
{
	int i, v;
	int *d = allocArray(n+1);
	
	for(i = 1; i <= n; i++)
		d[i] = oo;
	d[1] = 0;
	
	Q q = Q_New();
	Q_enqueue(q, 1);
	while( !Q_empty(q) )
	{
		v = Q_dequeue(q);
		for(i = 1; i < deg[v]; i++)
			if(d[ la[v][i] ] > d[v] + lc[v][i])
			{
				Q_enqueue(q, la[v][i] );
				d[ la[v][i] ] = d[v] + lc[v][i];
			}
	}
	for(i = 2; i <= n; i++)
		printf("%d ", d[i]);
	printf("\n");
	free(d);
}

void freeMem()
{
	int i;
	for(i = 1; i <= n; i++)
	{
		free(la[i]);
		free(lc[i]);
	}
	free(la), free(lc), free(deg);
}

int main()
{	
	freopen(filein, "rt", stdin);
	freopen(fileout, "wt", stdout);
	read();
	Bellman_Ford();
	freeMem();
	return 0;	
}