#include <fstream>
#include <vector>

using namespace std;

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

vector <int> nod_x,nod_y,cost;

int lungimea[50001],i,n,m;
short sem;

int main () {

	fin>>n>>m;
	int x,y,c;

	for (i=0; i<m; i++) 
	{
		fin>>x>>y>>c;
		nod_x.push_back(x);
		nod_y.push_back(y);
		cost.push_back(c);
	}

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