// http://infoarena.ro/problema/dijkstra
#include <fstream>
#include <vector>
#include <queue>
using namespace std;

#define cost first
#define location second
#define oo 0x3F3F3F3F

const int MAXSIZE = 50001;

ifstream in("dijkstra.in");
ofstream out("dijkstra.out");

int nodes,edges;
vector<int> dist(MAXSIZE,oo);
vector< pair<int,int> > graph[MAXSIZE];
priority_queue< pair<int,int>, vector< pair<int,int> >, greater< pair<int,int> > > myQueue;

void dijkstra(int startNode);

int main()
{
	in >> nodes >> edges;

	int from,to,cost;
	for(int i=1;i<=edges;i++)
	{
		in >> from >> to >> cost;
		graph[from].push_back(make_pair(cost,to));
	}

	dijkstra(1);

	for(int i=2;i<=nodes;i++)
		if(dist[i] == oo)
			out << "0 ";
		else
			out << dist[i] << " ";
	out << "\n";

	out.close();

	return (0);
}

void dijkstra(int startNode)
{
	dist[startNode] = 0;

	pair<int,int> currentNode;
	vector< pair<int,int> >::iterator neighbour,end;

	myQueue.push(make_pair(0,startNode));

	while(!myQueue.empty())
	{
		currentNode = myQueue.top();
		myQueue.pop();

		end = graph[currentNode.location].end();
		for(neighbour=graph[currentNode.location].begin();neighbour!=end;++neighbour)
			if(dist[neighbour->location] > dist[currentNode.location] + neighbour->cost)
			{
				dist[neighbour->location] = dist[currentNode.location] + neighbour->cost;
				myQueue.push(make_pair(dist[neighbour->location],neighbour->location));
			}
	}
}