# include <fstream>
# include <vector>
# include <queue>
# include <algorithm>
using namespace std;
const int maxn = 51000;
const int inf = 0x3f3f3f3f;
vector < pair <int, int> > G[maxn];
int dist [ maxn ],n,m;
bool viz [ maxn ];
priority_queue < pair <int, int>, vector < pair <int, int> >, greater < pair <int, int> > > h;
void Dijkstra()
{
	
	int minim;
	vector < pair <int, int> > :: iterator it;
	memset(dist, 0x3f, sizeof(dist));
	dist [ 1 ] = 0;
	h.push (make_pair(0 ,1));
	while (!h.empty())
	{
		minim = h . top () . second;
		h . pop();
		if ( viz [ minim ] )	continue;
		viz [ minim ] = true;
		for ( it = G[minim].begin(); it != G [ minim ]. end (); ++ it )
			if ( dist [ minim ] + it->first < dist [ it->second ] )
			{
				dist [ it->second ] = dist [ minim ] + it->first;
				h . push ( make_pair( dist [ it->second ], it->second ) );
			}
	}
}
int main ()
{
	int i, x, y, c;
	ifstream f ( "dijkstra.in" );
	ofstream g ( "dijkstra.out" );
	f >> n >> m;
	for ( i = 0; i < m; ++ i )
	{
		f >> x >> y >> c;
		G [ x ] . push_back ( make_pair(c, y) );
	}	
	Dijkstra ();
	for ( i = 2; i <= n; ++ i )
		if ( dist [ i ] != inf ) g << dist [ i ] << ' ';
			else g << "0 ";
	return 0;
}