#include <stdio.h>
#include <values.h>
#define Nmax 50001

int n, m, i, nrH;
int d[Nmax], h[Nmax], poz[Nmax];
struct graf { int nod, cost; graf * next; } * g[Nmax];

void dijkstra();
void heapup(int);
void heapdown(int);
inline void swap(int x, int y) { poz[h[x]]=y; poz[h[y]]=x; int temp=h[x]; h[x]=h[y]; h[y]=temp; }

int main()
{
	freopen("dijkstra.in", "r", stdin);
	scanf("%d %d\n", &n, &m);
	for (int x, y, z; m; m--)
	{
		scanf("%d %d %d\n", &x, &y, &z);
		graf * q = new graf;
		q->nod=y; q->cost=z; q->next=g[x]; g[x]=q;
	}
	dijkstra();
	freopen("dijkstra.out","w", stdout);
	for (i=2; i<=n; i++)
		printf("%d ", d[i]==MAXINT?0:d[i]);
	fclose(stdout);
	return 0;
}

void dijkstra()
{
	int x;
	for (i=2; i<=n; i++) d[i]=MAXINT;
	h[++nrH]=1; poz[1]=1;
	while (nrH)
	{
		x=h[1];
		swap(1,nrH);
		poz[h[1]]=1;
		nrH--;
		heapdown(1);
		for (graf * p = g[x]; p; p=p->next)
		{
			if (d[p->nod] > d[x] + p->cost)
			{
				d[p->nod] = d[x] + p->cost;
				if (poz[p->nod]) heapup(poz[p->nod]);
				else
				{
					h[++nrH]=p->nod; poz[p->nod]=nrH;
					heapup(nrH);
				}
			}
		}
	}
}

void heapup(int loc)
{
	if (loc<=1) return ;
	int tata = loc>>1;
	if (d[h[tata]] > d[h[loc]]) { swap(tata,loc); heapup(tata); }
}

void heapdown(int loc)
{
	int fiu;
	if (loc<<1 <= nrH) { fiu = loc<<1; if (fiu + 1 <= nrH && d[h[fiu+1]]<d[h[fiu]]) fiu++; }
	else return;
	if (d[h[fiu]] < d[h[loc]]) { swap(fiu,loc); heapdown(fiu); }
}