#include <stdio.h>
#include <vector>
using namespace std;
#define Max 50001
#define inf 0xffffff
vector<pair<int,int> >g[Max];

int n,m,d[Max],p[Max],nr;
struct heap{ int c,x; }h[Max];

void pop_heap()
{
	h[1]=h[nr--];
	p[h[1].x]=1;
	int t,f;
	t=1,f=2;
	if(f+1<=nr && h[f+1].c<h[f].c)f++;
	while(f<=nr)
	{
		swap(h[t],h[f]);
		swap(p[h[t].x],p[h[f].x]);
		t=f;f=2*t;
		if(f+1<=nr && h[f+1].c<h[f].c)f++;
	}
}

void push_heap(int x,int c)
{
	int t,f;
	if(p[x]==0)
	{
		nr++;
		p[x]=nr;
		h[nr].x=x;
		h[nr].c=c;
		f=nr;
	} else
	{
		f=p[x];
		h[f].x=x;
		h[f].c=c;
	}
	t=f/2;
	while(t>0 && h[f].c < h[t].c)
	{
		swap(h[t],h[f]);
		swap(p[h[t].x],p[h[f].x]);
		f=t; t=f/2;
	}
}

void dijkstra()
{
	int x,y,c;
	for(int i=2;i<=n;i++)d[i]=inf;
	h[1].c=0;
	h[1].x=1;
	p[1]=1;
	nr=1;
	while(nr>0)
	{
		x=h[1].x;
		c=h[1].c;
		pop_heap();
		for(int i=0;i<g[x].size();i++)
		{
			y=g[x][i].first;
			if(d[y]>c+g[x][i].second)
			{
				d[y]=c+g[x][i].second;
				push_heap(y,d[y]);
			}
		}
	}
}

int main()
{
	int x,y,c;
	freopen("dijkstra.in","r",stdin);
	freopen("dijkstra.out","w",stdout);
		scanf("%d %d",&n,&m);
		for(int i=1;i<=m;i++)
		{
			scanf("%d %d %d",&x,&y,&c);
			g[x].push_back(make_pair(y,c));
		}
		dijkstra();
		for(int i=2;i<=n;i++)printf("%d ",d[i]==inf?0:d[i]);
}