#include <iostream>
#include <vector>
#include <fstream>
#include <list>
#include <algorithm>

struct Nod
{
	Nod() : tentative(1<<15) {}
public:
	int tentative;
	std::vector< std::pair<int,int > > vecini;
};

std::vector<Nod> nodes(50005);
std::vector<int> visited(50005,0);
std::list<int> unvisitedQueue;
int n, m;

int findMinNode()
{
	int max = 1 << 16;
	int pos = -1;
	for ( int i = 1; i <= n; ++i )
	{
		if (visited[i] == 0 )
		{
			if ( nodes[i].tentative < max )
			{
				pos = i;
				max = nodes[i].tentative;
			}
		}
	}
	return pos;
}

void dijkstra( int source )
{
	nodes[source].tentative = 0;
	while ( 1 )
	{
		int head = findMinNode();
		if ( head == -1 ) return;
			
		for ( int i = 0; i < nodes[head].vecini.size(); ++i )
		{	
			if ( visited[nodes[head].vecini[i].first] != 1 )
			{
				int curentCost = nodes[nodes[head].vecini[i].first].tentative;
				if ( curentCost > nodes[head].tentative + nodes[head].vecini[i].second )
				{
					nodes[nodes[head].vecini[i].first].tentative = nodes[head].tentative + nodes[head].vecini[i].second;
				}
			}
		}
		visited[ head ] = 1;
	}
}

int main( int argc, char* argv[] )
{
	std::ifstream input ("dijkstra.in" );
	std::ofstream output ("dijkstra.out" );
	input >> n;
	input >> m;
	for ( int i = 0; i < m; ++i )
	{
		int f, s, a;
		input >> f; input >> s; input >> a;
		nodes[f].vecini.push_back( std::pair< unsigned int, unsigned int >( s, a ) );
	}

	dijkstra(1);

	for ( int i = 2; i <= n; ++i )
	{
		output << nodes[i].tentative << " ";
	}

	input.close();
	output.close();
	return 0;
};