#include<fstream>
#include<vector>

using namespace std;

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

int n,m,nh,d[MaxN],poz[MaxN],h[MaxN];
vector< pair<int,int> > G[MaxN];

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

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;
	m = i;
	if( L <= nh && d[h[L]] < d[h[m]] )
		m = L;
	if( R <= nh && d[h[R]] < d[h[m]] )
		m = R;
	if( m != i )
		{
			swap(h[m],h[i]);
			swap(poz[h[m]],poz[h[i]]);
			downheap(m);
		}
}

void solve()
{
	int nod,i;
	vector< pair<int,int> >::iterator it;
	for( i = 1 ; i <= n ; i++ )
		{
			d[i] = Inf;
			poz[i] = i;
			h[i] = i;
		}
	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]);
					}
		}
}

inline void print()
{
	ofstream g ("dijkstra.out");
	for( int i = 2 ; i <= n ; i++ )
		{
			if( d[i] == Inf )
				d[i] = 0;
			g << d[i] << ' ';
		}
	g << '\n';
	g.close();
}

inline void read()
{
	ifstream f("dijkstra.in");
	f >> n >> m;
	int x,y,cost;
	for( int i = 1 ; i <= m ; i++ )
		{
			f >> x >> y >> cost;
			G[x].push_back(make_pair(y,cost));
		}
	f.close();
}

int main()
{
	read();
	solve();
	print();
	return 0;
}