#include <fstream>
#include <vector>

using namespace std;

std::ifstream fin ("dijkstra.in");
std::ofstream fout ("dijkstra.out");

int lungimea[50001],i,n,m;
int nod_x[250001],nod_y[250001],cost[250001];
short sem;

int main () {

	fin>>n>>m;

	for (i=0; i<m; i++) 
	{
		fin>>nod_x[i]>>nod_y[i]>>cost[i];
	}

	for (i=0; i<=n; i++) 
		lungimea[i]=-1; 
	
	lungimea[1]=0;

	while(!sem)
	{
		sem=1;
		for (i=0; i<m; i++)
		{
			if (lungimea[nod_x[i]]>-1 && (lungimea[nod_y[i]]==-1 || lungimea[nod_y[i]] > lungimea[nod_x[i]]+cost[i])) 
			{
				lungimea[nod_y[i]]=lungimea[nod_x[i]]+cost[i];
				sem=0;
			}
		}
	}

	for (i=2; i<=n; i++)
		if (lungimea[i]==-1) 
			// nu exista drum
			fout << "0 ";
		else 
			fout << lungimea[i]<<" ";

	return 0;
}