#include <fstream>
#include <vector>
#include <string>
#include <algorithm>
#include <iostream>
#include <queue>
#include <map>
#include <cmath>
#include <set>
#include <cassert>

using namespace std;

#define INF (1<<29)

int n, m;

struct neighbor{
	int dest, cost;
	
	neighbor(int ddest, int ccost) : dest(ddest), cost(ccost) {}
};

vector<vector<neighbor> > adjacency_list;
vector<int> d;

void dijkstra(int source){
	d[source] = 0;
	std::set<std::pair<int, int> > vertex_queue;
	vertex_queue.insert(make_pair(source, d[source]));
	
	while(!vertex_queue.empty()){
		int nod = vertex_queue.begin()->first;
		int w = vertex_queue.begin()->second;
		vertex_queue.erase(vertex_queue.begin());
		
		for(unsigned i = 0; i < adjacency_list[nod].size(); ++i){
			neighbor& n = adjacency_list[nod][i];
			
			int costn = w + n.cost;
			
			if(costn < d[n.dest]){
				vertex_queue.erase(make_pair(nod, d[n.dest]));
				d[n.dest] = costn;
				vertex_queue.insert(make_pair(n.dest, costn));
			}
		}
	}
}

int main(){
	ifstream in("dijkstra.in");
	ofstream out("dijkstra.out");	
	
	in >> n >> m;
	
	adjacency_list.resize(n + 5);
	
	for(int i = 0; i < m; ++i){
		int x, y, w;
		in >> x >> y >> w;
		adjacency_list[x].push_back(neighbor(y, w));
	}
	
	d.resize(n+5, INF);
	
	dijkstra(1);
	
	for(int i = 2; i <= n; ++i){
		if(d[i] >= INF)
			out << 0 << " ";
		else
			out << d[i] << " ";
	}
	
	return 0;
}