#include <iostream>
#include <fstream>
using namespace std;
#define OO 999999999

ifstream f ("dijkstra.in");
ofstream g ("dijkstra.out");

struct nod
{
	nod *adr;
	int inf;
	int cost;
} *A[50001];

int n,m;
int d[50001];
int v[50001];

void Read ()
{
	f >> n >> m;
	int x,y,d;
	nod *p;
	for ( int i = 1; i <= m; i++ )
	{
		f >> x >> y >> d;
		p = new nod;
		p->inf = y;
		p->cost = d;
		p->adr = A[x];
		A[x] = p;
		
	}
}

void Dijkstra ()
{
	for ( int i = 2; i <= n ; i++ )
	{
		d[i] = OO;
	}
	
	int min, nmin;
	for ( int i = 1; i <= n ; i++ )
	{
		min = OO;
		
		for ( int j = 1 ; j <= n ; j++ )
			if ( d[j] < min && v[j] == 0 )
			{
				min = d[j];
				nmin = j;
			}
			
		v[nmin] = 1;
		
		nod *p = A[nmin];
		
		while ( p )
		{
			if ( d[p->inf] > d[nmin] + p->cost )
				d[p->inf] = d[nmin] + p->cost;
			p = p->adr;
		}
	}
}

void Write()
{
	for ( int i = 2; i <= n ; i++ )
		g << d[i] << ' ';
}

int main()
{
	Read();
	Dijkstra();
	Write();
}