#include <iostream>
#include <fstream>
#include <string>

using namespace std;

fstream in("dijkstra.in", ios::in);
fstream out("dijkstra.out", ios::out);

#define nmax 50005
#define inf 999999

struct nod
{
	int info,cost;
	nod *next;
} *lista[nmax], *p, *q;

int n,m,s[nmax],d[nmax];

int main()
{
	
	int i,j,c,mini,minp;

	in>>n>>m;

	while(in>>i>>j>>c)
	{
		p= new nod;
		p->info= j;
		p->cost= c;
		if(c == 0)
			p->cost= inf;
		if(i == 1)
			d[j]= p->cost;
		p->next= lista[i];
		lista[i]= p;
	}

	s[1]= 1;

	for(i=2;i<=n;i++)
		if(d[i] == 0)
			d[i] =inf;

	for(int k=1;k<n;k++)
	{
		mini= inf;
		p= lista[1];
		while(p)
		{
			if((d[p->info] <= mini) && (s[p->info] == 0))
			{
				mini= p->cost;
				minp= p->info;
				q= p;
			}
			p= p->next;
		}

		s[minp]= 1;

		p= lista[minp];

		while(p)
		{
			if(s[p->info] == 0)
				if( d[p->info] > (q->cost+ p->cost))
					d[p->info]= q->cost+ p->cost;
			p= p->next;
		}
	}

	for(i=2;i<=n;i++)
		out<< d[i]<< " ";
	



        
    in.close();
    out.close();

	return 0;
}