#include <iostream>
#include <set>
#include <vector>
#include <fstream>

using namespace std;

const int MAXN = 50000;
const int INF = 1000000000;

vector<int> COST[MAXN],DRUM[MAXN];
set < pair<int,int> > Ctemporar;

int N,M, d[MAXN];

void solutie()
{
	int x , val, costtemporar;
	for(int i = 2; i <= N; i++)
		d[i] = INF;
	Ctemporar.insert(make_pair(0,1));

	while(Ctemporar.size() > 0 )
	{
		val = (*Ctemporar.begin()).first , x = (*Ctemporar.begin()).second;
		Ctemporar.erase(*Ctemporar.begin());
		for(int i = 0; i < DRUM[x].size(); i++)
			if ( d[DRUM[x][i]] > val + COST[x][i])
			{
				d[DRUM[x][i]] = val + COST[x][i];
				Ctemporar.insert(make_pair(d[DRUM[x][i]],DRUM[x][i]));
			}		
	}
}

int main()
{
	ifstream f("djikstra.in");
	ofstream g("djikstra.out");

	f>>N>>M;
	int a,b,c;

	for(int i = 1; i <= M; i++)
	{
		f>>a>>b>>c;
		COST[a].push_back(c);
		DRUM[a].push_back(b);
	}

	solutie();

	for(int i = 2; i <= N ; i++)
		g<<(d[i] == INF ? 0 : d[i])<<" ";
	g.close();
}