#include<stdio.h>
#include<malloc.h>

#define INF 32000

using namespace std;

typedef struct _nod
{
	int info;
	int cost;
	struct _nod *adr;
} nod;

typedef struct
{
	struct _nod *cap;
} list;

long int n;
long int m;
int D[50001];
int S[50001];
list A[50001];

void add(int a,int b,int c)
{
	nod *nou = (nod*)malloc(sizeof(nod));
	nou->info = b;
	nou->cost = c;
	nou->adr = A[a].cap;
	A[a].cap = nou;
}

void citire(void)
{
	int a;
	int b;
	int c;
	FILE *f = fopen("dijkstra.in","r");
	
	fscanf(f,"%d %d",&n,&m);
	for(int i=1;i<=m;i++)
	{
		fscanf(f,"%d %d %d",&a,&b,&c);
		add(a,b,c);
	}
	
	fclose(f);
}

void complet(int poz)
{
	nod *q = A[poz].cap;
	while(q)
	{
		if(D[q->info] > D[poz] + q->cost)
			D[q->info] = D[poz] + q->cost;
		q = q->adr;
	}
}

void dijkstra(void)
{
	for(int i=1;i<=n;i++)
		D[i] = INF;
	D[1] = 0;
	int nr = 0;
	int poz = 1;
	int minim = 0;
	A[0].cap = NULL;
	while(nr<n-1 && minim != INF)
	{
		minim = INF;
		poz = 0;
		for(int i=1;i<=n;i++)
			if(D[i]<minim && !S[i])
			{
				minim = D[i];
				poz = i;
			}
		S[poz] = 1;
		if(poz) complet(poz);
		nr ++;
	}
}

int main()
{
	FILE *f = fopen("dijkstra.out","w");
	
	citire();
	dijkstra();
	
	for(int i=2;i<=n;i++)
		if(D[i] == INF)
		fprintf(f,"0 ");
		else
		fprintf(f,"%d ",D[i]);
	fclose(f);
	return 0;
}