#include <stdio.h>
#include<queue>
using namespace std;

int n,m,d[50002];

const int inf = 0x3f3f3f3f;

typedef struct nod
{
	int vec,pret;
	nod *urm;
} *pNod;
pNod v[50002];

void add(pNod &dest, int b,int c)
{
	pNod p;
	p = new nod;
	p -> vec = b;
	p -> pret = c;
	p -> urm = dest;
	dest = p;
}

void citire()
{
	freopen("dijkstra.in","r",stdin);
	freopen("dijkstra.out","w",stdout);
	scanf("%d %d",&n,&m);
	int i,a,b,c;

	for (i = 1; i <= m; i++)
	{
		scanf("%d %d %d",&a,&b,&c);
		add(v[a],b,c);
	}
}
int main()
{
	citire();
	
	int x,s,i;
	pNod p;
	queue <int> q;
	
	memset(d,inf,sizeof(d)); d[1]=0;
	
	q.push(1);
	while(!q.empty())
	{
		x=q.front();
		q.pop();
		for(p=v[x];p!=NULL;p=p->urm)
		{
			s=d[x]+p->pret;
			if(s<d[p->vec])
			{
				d[p->vec]=s; q.push(p->vec);
			}
		}
	}
	for(i=2;i<=n;i++) 
		if(d[i]==inf) printf("0 ");
		else printf("%d ",d[i]);
	return 0;
}