#include <fstream>
#include <vector>
#include <set>
using namespace std;
#define pb push_back
#define mp make_pair
#define OO 99999999

ifstream f ("dijkstra.in");
ofstream g ("dijkstra.out");

int n, m , d[50050];
vector < int > M[50050];
vector < int > C[50050];
set < pair < int, int > > T;

void Read ();
void Dijkstra ();
void Write ();

int main()
{
	Read ();
	Dijkstra();
	Write();
}

void Read ()
{
	int x,y,D;
	f >> n >> m;
	
	for ( int i = 1; i <= m ; i++ )
	{
		f >> x >> y >> D;
		M[x].pb(y);
		C[x].pb(D);
	}
}

void Dijkstra ()
{
	for ( int i = 1; i <= n; i++ )
			d[i] = OO;
		
	d[1] = 0;
	T.insert(mp(0,1));
	
	int cost, nod;
	
	while ( T.size() > 0 )
	{
		cost = (*T.begin()).first;
		nod  = (*T.begin()).second;
		T.erase(*T.begin());
		for ( unsigned int i = 0 ; i < M[nod].size(); i++ )
		{
			if ( d[ M[nod][i] ] > cost + C[nod][i] )
			{
				d[ M[nod][i] ] = cost + C[nod][i];
				T.insert ( mp ( d[ M[nod][i] ], M[nod][i] ) );
			}
		}
	}
}

void Write ()
{
	for ( int i = 2; i <= n ; i++ )
	{ 
		if ( d[i] == OO )
			g << 0 << ' ';
		else
			g << d[i] << ' ';
	}
}