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

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

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

int n,m;
int d[50001];
bool 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 = 1; i <= n ; i++ )
	{
		d[i] = OO;
	}
	
	int c[50001],p,u;
	
	p = u = 1;
	d[1] = 0;
	c[1] = 1;
	nod *x;
	int nc,ns;
	
	while ( p <=u )
	{
		ns = c[p];
		x = A[ ns ];
		v[ns] = 1;
		cout << ns << ' ';
		while ( x )
		{
			nc = x->inf;
			
			if ( v[nc] == 0 )
			{
				c[++u] = nc;
				if ( d[nc] > d[ns] + x->cost )
				{
					d[nc] = d[ns] + x->cost;
				}
			}
			x = x->adr;
		}
		p++;
	}
}

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

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