/*
Algoritm: Dijkstra cu heapuri

Complexitate: O( m * log(n) )

Observatii:
-Nodul de start a fost considerat nodul 1. Pentru a desemna alt nod de start sunt necesare cateva mici modificari;
-Prima pozitie a heapului este considerata 1. Astfel, tatal nodului i va fi i/2, fiul stanga i*2, iar fiul dreapta i*2+1;

*/
#include<stdio.h>
struct point 
{
	int x,c;
	point *y;
}*g[50001],*q; /* Folosim listele pentru a evita gasirea nodurilor vecine in O(n)*/
int m,n,i,j,k,x,y,c,h[50001],d[50001],p[50001],nod;
inline void intro(int x, int y, int c)
{
	point *q=new point;
	q->x=y;
	q->c=c;
	q->y=g[x];
	g[x]=q;
}
inline void swap(int i,int j)
{
	int x;
	x=h[i];
	h[i]=h[j];
	h[j]=x;
	x=p[h[i]];
	p[h[i]]=p[h[j]];
	p[h[j]]=x;
	/*Odata cu interschimbarea a doua elemente trebuie sa interschimbam si pozitiile lor in vectorul de pozitii*/
}
void heapup(int i)
{
	if(d[h[i/2]]<d[h[i]])return;
	swap(i,i/2);
	heapup(i/2);
}
void heapdown(int i)
{
	int st,dr;
	if(i*2>m) return;
	st=d[h[i*2]];
	if(i*2+1<=m)dr=d[h[i*2+1]];else dr=st+1;
	if(st<dr) 
	{
		if(d[h[i]]<=st)return;
		swap(i,2*i);
		heapdown(i*2);
	}
	else
	{
		if(d[h[i]]<=dr)return;
		swap(i,2*i+1);
		heapdown(2*i+1);
	}
}
int main()
{
	freopen("dijkstra.in","r",stdin);
	freopen("dijkstra.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(i=0;i<m;i++)
	{
		scanf("%d%d%d",&x,&y,&c);
		intro(x,y,c);
		intro(y,x,c);/* Aceasta instructiune va lipsi in cazul unui graf orientat*/
	}
	for(i=1;i<=n;i++)
	{
		d[i]=2000000000; /*Initial toate distantele sunt considerate infinit*/
		h[i]=i;
		p[i]=i;
	}
	m=n;
	d[1]=0;/*Toate distantele mai putin cea a nodului initial, bineinteles*/
	d[0]=-1;/*Acest lucru este oarecum util pentru cazurile cand costul dintre doua noduri este nul si considerati 1 prima pozitie a heapului*/
	for(i=0;i<n;i++)
	{
		nod=h[1];/*Desemnam nodul pe care il expandam*/
		swap(1,m); /*Dupa ce am ales nodul pe care il expandam, (cel din varful heapupul) il mutam la coada*/
		m--; /* si scadem lungimea heapului, astfel incat algoritmul va lasa nodul curent in pace*/
		heapdown(1); /*Reordonam arborele*/
		for(q=g[nod];q!=NULL;q=q->y) /*Luam fiecare nod vecin cu cel pe care il expandam*/
			if(d[q->x]>d[nod]+q->c) /*Verificam daca ajungem la el cu un cost mai bun*/
			{
				d[q->x]=d[nod]+q->c;/*Daca da, actualizam distanta, */
				heapup(p[q->x]);/*si reordonam heapul*/
			}
	}
	/*Scrierea*/
	for(i=2;i<=n;i++)
		if(d[i]==2000000000) printf("0 ");/* Daca are costul infinit ( adica 2000000000, asa cum am initializat mai sus, inseamna ca nu s-a putut ajunge la nod*/
		else printf("%d ",d[i]);
	return 0;
}