#include <fstream>

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];

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;

	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];
		}
	}

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

	return 0;
}