#include <fstream>
#include <iostream>
#include <vector>
#define INFINIT 2147483647
using namespace std;

vector <int> t[50001];
vector <int> c[50001];
long d[50001],N,M;
int viz[50001];

void calculeaza (long crt)
{
	viz[crt]=1;
	long i,lg=t[crt].size();
	for (i=0; i<lg; ++i)
		if (!viz[t[crt][i]] and d[t[crt][i]]>d[crt]+c[crt][i])
			d[t[crt][i]]=d[crt]+c[crt][i];
}

long cauta ()
{
	long i, imin=0;
	for (i=2; i<=N; ++i)
		if (d[i]<d[imin] and !viz[i]) imin=i;
	return imin;
}

int main ()
{
	long crt,i,j,a1,b1,c1;
	ifstream f("dijkstra.in");
	FILE *g; g=fopen("dijkstra.out", "w");
	f>>N>>M;
	for (i=1; i<=M; ++i)
	{
		f>>a1>>b1>>c1;
		t[a1].push_back(b1);
		c[a1].push_back(c1);
		d[i]=INFINIT;
	}
	d[0]=INFINIT;
	d[1]=0;
	crt=1;
	while (crt)
	{
		calculeaza(crt);
		crt=cauta();
	}
	for (i=2; i<=N; ++i)
		if (d[i]==INFINIT) fprintf(g, "0 ");
		else fprintf(g, "%u ", d[i]);
	f.close(); fclose(g);
	return 0;
}