#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
#define N 50010
#define M 250010
#define oo 1000
int a[N];
int viz[N];
int n , m ;

struct muchie
{
	int nod;
	int lungime;
};
vector <muchie> graf[N];
int minsir()
{
	int min = oo;
	int j = -1;
	for (int i = 1 ; i <= n ; ++i)
		if (!viz[i])
		{
			if (a[i] < min)
			{
				min = a[i];
				j = i;
			}
		}
	return j;
}
void golire()
{
	for (int i = 0 ; i <= n ; ++i )
		a[i] = oo;
}
int main()
{
	memset (viz , 0 , sizeof (viz));
	freopen ("dijkstra.in" , "r" , stdin);
	freopen ("dijkstra.out" , "w" , stdout);
	scanf ("%d %d" , &n , &m);
	int nn = n;
	golire();
	int x ;
	muchie y;
	for (int i = 0 ; i < m ; ++i)
	{
		scanf ("%d %d %d" , &x , &y.nod , & y.lungime);
		graf[x].push_back(y);
	}
	a[1] = 0;
	int s = 0;
	int suma = 0;
	int ok = 0;
	while (ok == 0)
	{
		int i = minsir();
		viz[i] = 1;
		if (i == -1)
			ok = 1;
		else
		{
			s = a[i];
			for (unsigned j = 0 ; j < graf[i].size() ; ++j)
			{
				suma = s + graf[i][j].lungime;
				if (suma < a[graf[i][j].nod])
					a[graf[i][j].nod] = s + graf[i][j].lungime;
			}
		}
	}
	for (int i = 1 ; i <= nn ; ++i)
		printf ("%d " , a[i]);
	return 0;
}