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

struct nod{
	vector<int> vecini;
	vector<int> distante;
};

vector<nod> muchii;
vector<int> distanta;
vector<bool> parcurs;

void relax(int u, int v, int w){
	if(distanta[u] != INT32_MAX && distanta[v] > distanta[u] + w){
		distanta[v] = distanta[u] + w;
	}
}


void Dijkstra(vector<nod> G, int start){
	auto comp = [&distanta](int x, int y){
		if(distanta[x] > distanta[y])
			return true;
		return false;
	};
	priority_queue<int, vector<int>, std::function<bool(int, int)>> q(comp);
	
	for(int i = 1; i <G.size(); i++){
		distanta[i] = INT32_MAX;
		parcurs.push_back(false);		
	}
	distanta[start] = 0;
	q.push(start);

	while(!q.empty()){
		int curent = q.top();
		q.pop();
		if(parcurs[curent] == false){
			for(int i =0; i < G[curent].vecini.size(); i++){
				relax(curent, G[curent].vecini[i], G[curent].distante[i]);
				q.push(G[curent].vecini[i]);
			}
		}
		parcurs[curent] = true;
	}

}



int main(){
	ifstream in("dijkstra.in");
	ofstream out("dijkstra.out");

	int n, m, x, y, z;
	in >> n >> m;
	muchii.resize(n+1);
	distanta.resize(n+1);

	for(int i = 0;i <m; i++){
		in >> x >> y >>z;
		muchii[x].vecini.push_back(y);
		muchii[x].distante.push_back(z);
	}

	
	Dijkstra(muchii, 1);

	for(int i = 2; i <distanta.size(); i++){
		out << distanta[i] << " ";
	}


}