#include <stdio.h>

#define Nmax 100001
#define NR 500000000
#define Cmax 500000

struct elem{
	int nod,cost;
	elem *next;
};
elem *p[Nmax];

int bell[Nmax],n,m,coada[Cmax],inceput=1,sfarsit=1;
char v[Nmax];

/* void initializare()
{
	int i;
	for(i=2;i<=n;++i)
		bell[i]=NR;
}*/

void adauga(int x, int y, int c)
#include <stdio.h>

#define Nmax 100001
#define NR 500000000
#define Cmax 500000

struct elem{
	int nod,cost;
	elem *next;
};
elem *p[Nmax];

int bell[Nmax],n,m,coada[Cmax],inceput=1,sfarsit=1;
char v[Nmax];

/* void initializare()
{
	int i;
	for(i=2;i<=n;++i)
		bell[i]=NR;
}*/

void adauga(int x, int y, int c)
{
	elem *current=new elem;
	current->nod=y;
	current->cost=c;
	current->next=p[x];
	p[x]=current;
}

void relax(int x)
{
	elem *current=p[x];
	while(current)
		{
		if(bell[current->nod]==0)
			{
				if(v[current->nod]==0)
						{
							bell[current->nod]=bell[coada[inceput]]+current->cost;
							if(v[current->nod]==0)
								{
									coada[++sfarsit]=current->nod;
									v[current->nod]=1;
								}
						}
		  //	current=current->next;
			}
		else
			if(bell[x]+current->cost<bell[current->nod])
				{
					bell[current->nod]=bell[coada[inceput]]+current->cost;
					if(v[current->nod]==0)
						{
							coada[++sfarsit]=current->nod;
							v[current->nod]=1;
						}
				}
		current=current->next;
		}
}


void sol()
{
	while(inceput<=sfarsit)
		{
			relax(coada[inceput]);
			v[coada[inceput]]=0;
			++inceput;
		}
}

int main()
{
	int x,y,c,i;
	freopen("dijkstra.in","r",stdin);
	freopen("dijkstra.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(i=1;i<=m;++i)
		{
			scanf("%d%d%d",&x,&y,&c);
			adauga(x,y,c);
		}
//	initializare();
	coada[1]=1;
	sol();
	for(i=2;i<=n;++i)
		{
			if(bell[i]!=NR)
				printf("%d ",bell[i]);
			else
				printf("0 ");
		}
	return 0;
}