#include <fstream>
#include <vector>
#include <set>
using namespace std;

ifstream is("dijkstra.in");
ofstream os("dijkstra.out");

#define INF 0x3f3f3f3f
#define pb push_back

vector<vector<pair<int, int> > > G;
vector<int> Cost;
set<pair<int, int> > Q;
int i, j, cost;
int Ok[50001];
int n, m;

void Dijkstra(int k);
void Read();
void Write();

int main()
{
	Read();
	Dijkstra(1);
	Write();
	is.close();
	os.close();
	return 0;
}

void Read()
{
	is >> n >> m;
	G.resize(n + 1);
	Cost.resize(n + 1, INF);
	for ( int p = 1; p <= m; ++p )
	{
		is >> i >> j >> cost;
		G[i].pb( {cost, j} );
	}
}
void Dijkstra(int k)
{
	int t;
	Cost[k] = 0;
	Q.insert( {0, k});
	while ( !Q.empty() )
	{
		cost = Q.begin()->first;
		i = Q.begin()->second;
		Q.erase(Q.begin());
		if ( Ok[i] ) continue;
		Ok[i] = true;
		for ( const auto& y : G[i] )
		{
			t = y.first;
			j = y.second;
			if ( Cost[j] > cost + t )
			{
				Cost[j] = cost + t;
				Q.insert( {Cost[j], j});
			}
		}
	}
}

void Write()
{
	for ( vector<int>::iterator it = Cost.begin() + 2; it != Cost.end(); ++it )
		if ( *it == INF )
			os << 0 << ' ';
		else
			os << *it << ' ';
}