// O(M lg M)

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

ifstream F("dijkstra.in");
ofstream G("dijkstra.out");

#define key second
#define val first

#define Nmax 50011
#define Mmax 250011
#define oo 1<<30

priority_queue < pair<int,int> , vector< pair<int,int> > , greater< pair<int,int> > > H;
vector< pair<int,int> > A[Nmax];
vector< pair<int,int> > Aux;

int N,M;
int Used[Nmax];
int Distance[Nmax];

void Insert_neighbour( int key )
{
	while ( A[key].size() )
	{
		Aux.push_back( A[key].back() );
		A[key].pop_back();
		
		int Val=Aux.back().val + Distance[key];
		int Key=Aux.back().key;
		
		if ( !Used[Key] )
			H.push( make_pair( Val , Key ) );
	}
	while ( Aux.size() )
	{
		A[key].push_back( Aux.back() );
		Aux.pop_back();
	}	
}

int main()
{
	F>>N>>M;
	for (int i=1;i<=M;++i)
	{
		int a,b,c;
		F>>a>>b>>c;
		A[a].push_back( make_pair( c , b ) );
	}
	
	int Start=1;
	
	for (int i=1;i<=N;++i)
		Distance[i]=oo;
	
	Distance[Start]=0;
	Used[Start]=1;
	Insert_neighbour( Start );
	
	while ( Used[ H.top().key ] ) H.pop();
	
	while ( H.size() )
	{
		int Val = H.top().val ;
		int End = H.top().key ;
		Distance[End]=Val;
		Used[End]=1;
		
		H.pop();
		Insert_neighbour( End );
		
		if ( H.size() )
			while ( Used[ H.top().key ] ) 
			{
				H.pop();
				if ( H.empty() ) break;
			}
	}
	
	for (int i=2;i<=N;++i)
		if ( Used[i] )
			G<<Distance[i]<<' ';
		else
			G<<"0 ";
	G<<'\n';
}