#include <iostream>
#include <fstream>
#include <vector>
#include <queue>

#define MAX	50001
#define INF	9999999


unsigned int n, m;
int dist[MAX];
bool visited[MAX];

class Compare
{
public:
	bool operator() (int a, int b)
	{
		return dist[a] > dist[b];
	}
};


std::vector <std::vector <std::pair<int, int> > > edges;
std::priority_queue <int, std::vector<int>, Compare> pq;


int main ( void )
{
	freopen( "dijkstra.in", "r", stdin );
	freopen( "dijkstra.out", "w", stdout );

	std::cin >> n >> m;

	edges.resize(n + 1);

	int in, out, cost;
	for( unsigned int i = 0; i < m; ++i )
	{
		std::cin >> in >> out >> cost;
		edges[in].push_back( std::make_pair(out, cost) );
	}

	dist[1] = 0;
	for( unsigned int i = 2; i <= n; ++i )
	{
		dist[i] = INF;
	}

	pq.push(1);
	while( !pq.empty() )
	{
		int curr = pq.top();
		pq.pop();
		visited[curr] = true;

		for( std::vector< std::pair <int, int> >::iterator it = edges[curr].begin();
			 it != edges[curr].end(); 
			 ++it )
		{
			if( visited[curr] && dist[it -> first] > dist[curr] + it -> second)
			{
				dist[it -> first] = dist[curr] + it -> second;
				pq.push( it -> first );
			}
		}
	}

	for( unsigned int i = 2; i <= n; ++i )
	{
		dist[i] == INF ? std::cout << 0 << ' ' : std::cout << dist[i] << ' ';
	}

	std::cout << "\n";

	fclose( stdin );
	fclose( stdout );
	return 0;

}