#include<fstream>
#include<cstdio>
#include<vector>

using namespace std;

#define T ((i)/2)
#define L ((i)*2)
#define R ((i)*2+1)

const int MaxN = 50001;
const int INF = 0x3f3f3f3f;

const char InFile[] = "dijkstra.in";
const char OutFile[] = "dijkstra.out";

int N,M,Nh,d[MaxN],poz[MaxN],H[MaxN];
vector< pair<int,int> >G[MaxN];

void upheap(int i)
{
	if( i > 1 )
		if( d[H[i]] < d[H[T]] )
			{
				swap( H[i] , H[T] );
				swap( poz[H[i]] , poz[H[T]]);
				upheap(T);
			}
}

void downheap(int i)
{
	int m = i;
	if( L <= Nh && d[H[m]] > d[H[L]] )
		m = L;
	if( R <= Nh && d[H[m]] > d[H[R]] )
		m = R;
	if( m != i )
		{
			swap(H[i],H[m]);
			swap(poz[H[i]],poz[H[m]]);
			downheap(m);
		}
}

void dijkstra()
{
	int nod;
	vector< pair<int,int> >::iterator it;
	for( nod = 1 ; nod <= N ; ++nod )
		{
			d[nod] = INF;
			poz[nod] = H[nod] = nod;
		}
	d[1] = 0;
	Nh = N;
	while( Nh )
		{
			nod = H[1];
			swap( H[1],H[Nh] );
			swap( poz[H[1]],poz[H[Nh]] );
			--Nh;
			downheap(poz[H[1]]);
			for( it = G[nod].begin() ; it != G[nod].end() ; ++it )
				if( d[it->first] > d[nod] + it -> second )
					{
						d[it->first] = d[nod] + it->second;
						upheap(poz[it->first]);
					}
		}
}

int main()
{
	int i,x,y,cost;
	ifstream fin( InFile );
	ofstream fout( OutFile );
	fin >> N >> M;
	for( i = 0 ; i < M ; ++i )
		{
			fin >> x >> y >> cost;
			G[x].push_back(make_pair(y,cost));
		}
	dijkstra();
	for( i = 2 ; i <= N ; ++i )
		if( d[i] < INF )
			fout << d[i] << ' ';
			else
			fout << "0 ";
	fout << '\n';
	fin.close();
	fout.close();
	return 0;
}