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

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

const long long inf = 1e12;

struct dj_node {
	int node;
	long long distance;
};



class Heap{
	private:
		vector<dj_node> values;
		int num_values;

		void shift_up(int index){
			if (index == 1){
				return;
			}

			int father = index/2;
			if (values[index].distance < values[father].distance) {
				swap(values[father], values[index]);
				shift_up(father);
			}
		}

		void shift_down(int index) {
			int left = index * 2, right = index *2 +1;

			if (right > num_values && left > num_values) {
				return;
			}

			if (right > num_values) {
				if (values[index].distance > values[left].distance){
					swap(values[index], values[left]);
					shift_down(left);
				}
			} else {
				int a = left, b= right;
				if (values[b].distance < values[a].distance){
					swap(a, b);
				}

				if (values[index].distance > values[a].distance){
					swap(values[index], values[a]);
					shift_down(a);
				}
			}
		}

	public:

		Heap(): values(1), num_values(0) {

		}

		bool empty() {
			return num_values == 0;
		}

		void insert(dj_node node) {
			values.push_back(node);
			num_values++;
			shift_up(num_values);
		}

		// Return exception if there are no values here.
		dj_node top() {
			return values[1];
		}

		void pop() {
			swap(values[1], values[num_values]);
			num_values--;
			values.pop_back();
			shift_down(1);
		}
};

struct edge{
	int to, distance;
};
int n, m;
vector<vector<edge>> graph;

void read(){
	in>>n>>m;
	graph.resize(n);
	int a, b, c;
	
	for (int i=0;i<m;i++){
		in>>a>>b>>c;
		graph[a-1].push_back({b-1, c});
	}
}

void dijkstra(){
	vector<long long> distances(n, inf);
	Heap h;
	h.insert({0, 0});
	distances[0] = 0;

	while(!h.empty()) {
		dj_node	top = h.top();
		h.pop();

		if (top.distance > distances[top.node]) {
			continue;
		}

		for(const edge& e: graph[top.node]) {
			long long cost = top.distance + e.distance;
			if (cost < distances[e.to]) {
				distances[e.to] = cost;
				h.insert({e.to, cost});
			}
		}
	}

	for (int i =1;i<n;i++){
		if (distances[i] == inf) {
			distances[i] = 0;
		}
		out<<distances[i]<<" ";
	}
}


int main(){
	read();
	dijkstra();

	return 0;
}