#include <stdio.h>
#include <limits.h> 
#include <queue>
#include <algorithm>

#define nmax 50005
#define mmax 250005
#define inf INT_MAX
#define dist first 
#define nod second 

using namespace std;

typedef pair <int, int> ii;
typedef vector <ii> vii;

int n, m;
vector <int> d (nmax, inf);
vector <vii> g (nmax);
priority_queue <ii, vii, greater <ii> > q; 


void scan ()
{
	int i, a, b, c;
	scanf ("%d%d\n", &n, &m);
	for (i=1; i <= m; ++i)
	{
		scanf ("%d%d%d", &a, &b, &c);
		g [a].push_back (make_pair (c, b));
	}	
}

void dijkstra ()
{
	ii top;
	vii::iterator it;
	d [1]=0;
	q.push (make_pair (0, 1));
	while (!q.empty ())
	{
		top=q.top ();	
		q.pop ();
		if (top.dist == d [top.nod])
		{
			for (it=g [top.nod].begin (); it != g [top.nod].end (); ++it)
				if (top.dist + it->dist < d [it->nod])
				{
					d [it->nod]=top.dist + it->dist;
					q.push (make_pair (d [it->nod], it->nod));
				}	
		}	
	}	
}

void print ()
{
	int i;
	for (i=2; i <= n; ++i) 
		if (d [i] != inf)
		       printf ("%d ", d [i]);
		else
			printf ("0 ");
	printf ("\n");	
}

int main ()
{
	freopen ("dijkstra.in", "r", stdin);
	freopen ("dijkstra.out", "w", stdout);
	scan ();
	dijkstra ();
	print ();
	return 0;
}