#include <iostream>
#include <fstream>
#include <vector>
#include <utility>
#include <queue>

#define MAX  666133

using namespace std;

queue<pair<int,int>> q;

vector<vector<pair<int,int>>> adiacenta;
vector<int> distances;

void dijkstra(){

	pair<int, int> p, r;
	while(q.size()){
		p = q.front();
		q.pop();
		for(int i = 0; i < adiacenta[p.first].size(); i++){
			r = adiacenta[p.first].at(i);
			if(distances[r.first] > distances[p.first] + r.second){
				distances[r.first] = distances[p.first] + r.second;
			}
			q.push(r);
		}
	}
}


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

	int n, m, a, b, cost;

	fin >> n >> m;

	vector<pair<int,int>> v;
	for(int i = 0; i < n; i++){
		adiacenta.push_back(v);
		distances.push_back(MAX);
	}
	distances[0] = 0;

	for(int i = 0; i < m; i++){
		fin >> a >> b >> cost;
		adiacenta[--a].push_back(make_pair(--b,cost));
	}

	q.push(make_pair(0,0));
	dijkstra();

	for(int i = 1; i < n; i++){
		fout << distances[i] << " ";
	}
	fout << "\n";
	return 0;
}