#include <fstream>
#include <iostream>
#include <queue>
#include <list>
#include <vector>
#include <bits/stdc++.h>
using namespace std;

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

int m, n;
const int inf = 1<<30; 
vector<int> dist (50001, inf);

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

 struct compare  
 {  
   bool operator()(const int& n1, const int& n2)  
   {  
       return dist[n1]>dist[n2];
   }  
 };
	priority_queue<int, vector<int>, compare > q;

void dijkstra (vector<list<Node> >graph){
	//vector<int> cost(n+1, 0);
	//bitset<inf> dealtWith;
	int d;	
	dist[1] = 0;
	for (int i = 2; i <= n; ++i)
		q.push(i);
	q.push(1);

	/*//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()){
		int u = q.top();
		q.pop();
		//if (dealtWith[u.value] == true)
		//	continue;
		//else 
		//	dealtWith[u.value] = true;
		list<Node> aux = graph[u];
		list<Node>::iterator it;
		for (it = aux.begin(); it!=aux.end();++it)
		{
			d = dist[u] + 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)
	{
		if (dist[i] == inf)
			dist[i] = 0;
		g<<dist[i]<<" ";
	}
}

int main () {
	int a, b, c;
	Node aux;
	f>>n>>m;

	vector<list<Node> > graph(n+1);
	for (int i = 1; i<=m; ++i)
	{
		f >> a >> b >> c;
		aux.lung = c;
		aux.value = b; 
		graph[a].push_back(aux);
	}
	dijkstra(graph);
}