#include <algorithm>
#include <cstdio>
#include <vector>
#define nmax 50005
#define pb push_back 
#define mp make_pair
#define f first
#define s second
const int inf = 1 << 30; 
using namespace std;
int heap[nmax],d[nmax],n,m,L,p[nmax];
vector <pair <int, int> > a[nmax];
void up_heap(int x)
{
	int aux;
	while (x>>1 && d[heap[x]]<d[heap[x>>1]])
	{
		aux=heap[x];
		heap[x]=heap[x>>1];
		heap[x>>1]=aux;
		p[heap[x]]=x;
		p[heap[x>>1]]=x>>1;
		x>>=1;
	}
}
void down_heap(int x)
{
	int aux,y=0;
	while (y!=x)
	{
		y=x;
		if (y*2<=L && d[heap[x]]>d[heap[y*2]])
			x=y*2;
		if (y*2+1<=L && d[heap[x]]>d[heap[y*2+1]])
			x*=y*2+1;
		aux=heap[x];
		heap[x]=heap[y];
		heap[y]=aux;
		p[heap[x]]=x;
		p[heap[y]]=y;
	}
}


int main()
{
	freopen("dijkstra.in","r",stdin);
	freopen("dijkstra.out","w",stdout);
	int i,x,y,z;
	scanf("%d%d",&n,&m);
	for (i=1; i<=m; ++i)
	{
		scanf("%d%d%d",&x,&y,&z);
		a[x].pb(mp(y,z));
	}
	for (i=1; i<=n; ++i)
		d[i]=inf;
	heap[++L]=1;int min;
	d[1]=0; p[1]=1;int g,h;
	while (L)
	{
		min=heap[1];		
		heap[1]=heap[L--];
		p[heap[1]]=1;
		down_heap(1);
		for (i=1; i<=a[min].size(); ++i)
		{
			g=a[min][i-1].s;
			h=a[min][i-1].f;
			if (d[h] > d[min]+a[min][i-1].s)
				d[h] = d[min]+a[min][i-1].s;
			if (p[a[min][i-1].f])
				up_heap(p[a[min][i-1].f]);
			else
			{
				heap[++L]=a[min][i-1].f;
				p[heap[L]]=L;
				up_heap(L);
			}
		}
	}
	for (i=2;i<=n;++i)
		if (d[i]!=inf)
			printf("%d ",d[i]);
		else
			printf("0 ");
	return 0;
}