#include <stdio.h>
#include <vector>
#define NMAX 50001
#define INF 1000000000
#define pb push_back
#define mp make_pair
#define f first
#define s second
using namespace std;
int n,m,r,cost[NMAX];
vector < pair <int,int> > v[NMAX];
struct heap
{
	int a,b;
};
heap A[NMAX];
void read()
{
	scanf("%d%d",&n,&m);
	int i,x,y,z;
	for (i=1; i<=m; i++)
	{
		scanf("%d%d%d",&x,&y,&z);
		v[x].pb(mp(y,z));
	}
}
void init()
{
	int i;
	for (i=2; i<=n; i++)
		cost[i]=INF;
}
void interschimba(int x,int y)
{
	int f,g;
	f=A[x].a; g=A[x].b;
	A[x].a=A[y].a; A[x].b=A[y].b;
	A[y].a=f; A[y].b=g;
}
void muta_in_jos(int nod)
{
	int minimum;
	if (2*nod<=r)
	{
		minimum=nod;
		if (A[2*nod].b<A[nod].b)
			minimum=2*nod;
		if (2*nod+1<=r && A[2*nod+1].b<A[minimum].b)
			minimum=2*nod+1;
		if (minimum!=nod)
		{
			interschimba(nod,minimum);
			muta_in_jos(minimum);
		}
	}
}
void muta_in_sus(int nod)
{
	if (nod>1 && A[nod/2].b>A[nod].b)
	{
		interschimba(nod/2,nod);
		muta_in_sus(nod/2);
	}
}
void dijkstra()
{
	A[++r].a=1;
	int i,x,y;
	while (r)
	{
		x=A[1].a; y=A[1].b;
		A[1]=A[r];  r--; //stergere din heap
		muta_in_jos(1);
		for (i=0; i<v[x].size(); i++)
			if (y+v[x][i].s<cost[v[x][i].f])
			{
				cost[v[x][i].f]=y+v[x][i].s;
				A[++r].a=v[x][i].f; //adaugare heap
				A[r].b=y+v[x][i].s;
				muta_in_sus(r);
			}
	}
}
void show()
{
	int i;
	for (i=2; i<=n; i++)
		printf("%d ",cost[i]==INF ? 0 : cost[i]);
	printf("\n");
}
int main()
{
	freopen("dijkstra.in","r",stdin);
	freopen("dijkstra.out","w",stdout);
	read();
	init();
	dijkstra();
	show();
	return 0;
}