using namespace std;
#include <cstdio>
#include <queue>
#include <string>
#define oo 0x3f3f3f3f
#define N 50001
#define DIM 8192

char ax[DIM];
int pz;

inline void cit(int &x)
{
	x=0;
	while(ax[pz]<'0' || ax[pz]>'9')
		if(++pz==DIM)fread(ax,1,DIM,stdin),pz=0;
	while(ax[pz]>='0' && ax[pz]<='9')
	{
		x=x*10+ax[pz]-'0';
		if(++pz==DIM)fread(ax,1,DIM,stdin),pz=0;
	}
}

struct nod { int x, c;nod*n;};

nod *a[N];
int d[N], n, m;

void dijkstra()
{
	queue<int>Q;
	memset(d, oo, sizeof(d));
	d[1]=0;
	Q.push(1);
	
	while(!Q.empty())
	{
		int u=Q.front();
		Q.pop();
		
		for(nod *i=a[u]; i ; i=i->n)
			if(d[u] + i->c < d[i->x])
			{
				d[i->x]= d[u] + i->c;
				Q.push(i->x);
			}
	}

	for(int i=2;i<=n;++i) 
		if(d[i]!=oo) printf("%d ", d[i]);
		else printf("0 ");
		
}

int main()
{
	freopen("dijkstra.in","r",stdin);
	freopen("dijkstra.out","w",stdout);
	cit(n);cit(m);
	int p, q, c;
	while(m--)
	{
		cit(p);cit(q);cit(c);
		nod *t=new nod;
		t->x=q;
		t->c=c;
		t->n=a[p];
		a[p]=t;
	}

	dijkstra();
	return 0;
}