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

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

#define val first 
#define key second

typedef pair<int,int> Grupe;
typedef Grupe Heap[Nmax];

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

#define cost first
#define nod second

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

Heap H;int Size;
int Used[Nmax];
int Distance[Nmax];
int N,M;

Grupe Null;
int Poz[Nmax];

void UpHeap( Heap H, int Size , int Nod )
{
	int p=H[Nod].key;
	while ( H[Nod].val < H[Nod/2].val && Nod/2 )
	{
		swap( Poz[p] , Poz[H[Nod/2].key] );
		swap( H[Nod] , H[Nod/2] );
		Nod/=2;
	}
}

void DownHeap( Heap H , int Size , int Nod )
{
	int p=1;
	while ( p )
	{
		p=0;
        if ( 2*Nod <= Size ) 
		{
            p = 2*Nod; 
            if ( ( 2*Nod < Size ) && ( H[ 2*Nod+1 ].val < H[ 2*Nod ].val ) ) ++p; 
            if ( H[p].val >= H[Nod].val ) p=0;
        }
        if ( p ) 
		{
			swap( Poz[H[Nod].key] , Poz[H[p].key] );
            swap( H[Nod],H[p] );
			Nod=p;
        }
	}
}

void Insert( Heap H, int& Size , Grupe Value )
{
	H[++Size]=Value;
	Poz[ H[Size].key ]=Size;
	UpHeap(H,Size,Size);
}

void Earse( Heap H ,int& Size , int Nod)
{
	swap( H[Nod],H[Size] );
	swap( Poz[H[Nod].key] , Poz[H[Size].key] );
	
	Poz[H[Size].key]=0;
	H[Size]=Null;
	--Size;
	
	if ( Nod<Size ) 
		DownHeap(H,Size,Nod);
}

void Insert_neighbour( int Nod )
{
	while ( A[Nod].size() )
	{
		Aux.push_back( A[Nod].back() );
		A[Nod].pop_back();
		
		int Val=Aux.back().cost + Distance[Nod];
		int Key=Aux.back().nod;
		
		if ( !Poz[Key] && !Used[Key] )
			Insert( H , Size , make_pair( Val,Key ) );
		else
			if ( !Used[Key] && Val < H[ Poz[Key] ].val )
			{
				Earse( H , Size , Poz[Key] );
				Insert( H , Size , make_pair( Val,Key ) );
			}
	}
	while ( Aux.size() )
	{
		A[Nod].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 );
	
	for ( ; Size; )
	{
		while ( Used[ H[1].key ] ) 
			Earse( H, Size , 1 );
		
		int Val = H[1].val ;
		int End = H[1].key ;
		Distance[End]=Val;
		Used[End]=1;
		
		Earse( H, Size , 1 );
		Insert_neighbour( End );
	}
	
	for (int i=2;i<=N;++i)
		G<<Distance[i]<<' ';
	G<<'\n';
}