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

#define INFINITY 0x3f3f3f3f
#define maxSize 50001
#define location second
#define cost first

int nodes;
vector<int> dist;	// se justifica folisirea vector prin prisma utilizarii assign si replace_if
list< pair<int,int> > graph[maxSize];
priority_queue< pair<int,int>, vector< pair<int,int> >, greater< pair<int,int> > > myHeap;

void read();
void dijkstra(int startNode);
bool isInf(int number) { return (number == INFINITY); };
void write();

int main() {
	read();
	dijkstra(1);
	write();

	return (0);
}

void read() {
	ifstream in("dijkstra.in");
	int edges,from,to,cost;

	in >> nodes >> edges;
	dist.resize(nodes+1);

	for(int i=1;i<=edges;i++) {
		in >> from >> to >> cost;

		graph[from].push_back(make_pair(cost,to));	// graful este orientat
	}

	in.close();
}

void dijkstra(int startNode) {
	dist.assign(nodes+1,INFINITY);
	dist[startNode] = 0;

	pair<int,int> currentNode;
	list< pair<int,int> >::iterator neighbour;

	myHeap.push(make_pair(0,startNode));	// se introduce nodul de pornire in heap

	while(!myHeap.empty()) {
		currentNode = myHeap.top();	// se extrage minimul
		myHeap.pop();	// se elimina nodul extras

		for(neighbour=graph[currentNode.location].begin();neighbour!=graph[currentNode.location].end();neighbour++)
			// daca se poate imbunatatii costul
			if(dist[neighbour->location] > dist[currentNode.location] + neighbour->cost) {
				dist[neighbour->location] = dist[currentNode.location] + neighbour->cost;	// se imbunatateste
				myHeap.push(make_pair(dist[neighbour->location],neighbour->location));	// se introduce in heap
			}
	}
}

void write() {
	ofstream out("dijkstra.out");
	replace_if(dist.begin(),dist.end(),isInf,0);

	for(int i=2;i<=nodes;i++)
			out << dist[i] << " ";

	out.close();
}