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

vector <int> nod[50001];
vector <int> dist[50001];
int viz[50001];
unsigned long long d[50001];
long i,j,m,n,a,b,c,nviz,crt,val;


void actualizare (long crt)
{
	long i,k=nod[crt].size();
	viz[crt]=1;
	for (i=0; i<k; i++)
	{
		if (!viz[nod[crt][i]])
			if (d[nod[crt][i]]>dist[crt][i]+d[crt])
				d[nod[crt][i]]=dist[crt][i]+d[crt];
	}
}

long cautamin ()
{
	long i,min=INFINIT,imin=0;
	for (i=2; i<=n; i++) 
		if (d[i]<min and !viz[i]) 
		{
			imin=i;
			min=d[i];
		}
	return imin;
}

int main ()
{
	FILE *f,*g;
	f=fopen("dijkstra.in", "r");
	g=fopen("dijkstra.out", "w");
	fscanf(f, "%d %d", &n,&m);
	for (i=1; i<=m; i++)
	{
		fscanf(f, "%d", &a);
		fscanf(f, "%d", &b);
		fscanf(f, "%d", &c);
		nod[a].push_back(b);
		dist[a].push_back(c);
	}
	fclose(f);
	//initial
	nviz=n;
	d[1]=0;
	for (i=2; i<=n; i++) d[i]=INFINIT;
	

	crt=1;
	while (crt)
	{
		actualizare(crt);
		crt=cautamin();
	}
	
	for (i=2; i<=n; i++) fprintf(g, "%d ", d[i]);
	
	//for (i=1; i<=n; i++) cout<<d[i]<<"("<<viz[i]<<") ";
	//cout<<"\n";
	
	
	//for (i=1; i<=n; i++)
	//{
	//	for (j=0; j<nod[i].size(); j++)
	//		cout<<nod[i][j]<<" ("<<dist[i][j]<<") ";
	//	cout<<"\n";
	//}
	fclose(g);
	return 0;
}