#include <fstream>
#include <iostream>
#include <queue>
#include <list>
#include <vector>
using namespace std;

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

int m, n;
const int inf = 1<<30; 

struct Node {
	int lung;
	int value;
	bool operator> (const Node& nod){
		if (this->lung >nod.lung)
			return true;
		else
			return false;
	}
};

 struct compare  
 {  
   bool operator()(const Node& n1, const Node& n2)  
   {  
       return n1.lung>n2.lung;  
   }  
 };

vector<list<Node> > graph(50000);
vector<int> prev(50001);

void dijkstra (){
	vector<int> dist (n+1, inf);
	vector<int> cost(n+1);
	priority_queue<Node, vector<Node>, compare > q;
	int d;
	Node firstNode;
	firstNode.value = 1;
	
	dist[1] = 0;
	q.push(firstNode);

	/*//test
	firstNode.lung = 3;
	q.push(firstNode);
	firstNode.lung = 8;
	q.push(firstNode);
	firstNode.lung = 5;
	q.push(firstNode);
	cout<<"test:"<<endl;
	while (!q.empty())
	{
		Node a = q.top();
		cout<<a.lung<< " ";
		q.pop();
	}
	return;
	*/
	while (!q.empty()){
		Node u = q.top();
		q.pop();
		list<Node> aux = graph[u.value];
		list<Node>::iterator it = aux.begin();

		for (it = aux.begin(); it!=aux.end();++it)
		{
			d = dist[u.value] + it->lung;
			if (d < dist[it->value])
			{
				dist[it->value] = d;
				//prev[it->value] = u.value;
			}
			q.push (*it);
		}
	}
	for (int i = 2; i<=n; ++i)
		g<<dist[i]<<" ";
}

int main () {
	int a, b, c;
	Node aux;
	f>>n>>m;
	for (int i = 1; i<=m; ++i)
	{
		f >> a >> b >> c;
		aux.lung = c;
		aux.value = b; 
		graph[a].push_back(aux);
	}
	//test
	/*for (int i = 1; i<=n; ++i)
	{
		list<Node> aux = graph[i];
		list<Node>::iterator it = aux.begin();
		for (it=aux.begin();it != aux.end();++it)
			cout<<it->value<<" ";
		cout<<endl;
	}*/
	dijkstra();
}