#include <fstream>
#include<iostream>
#include <vector>
#include <algorithm>
#include <queue>
#define NMAX 50005
#define INF 1000000000
using namespace std;

struct Edges {
	int start, end;
	int cost;
};

struct comp {
	bool operator()(pair<int,int> &a, pair<int,int> &b) {
		return a.second > b.second;	
	}

};

int d[NMAX];

vector<pair<int,int>> graf[NMAX];
priority_queue<pair<int,int>, vector<pair<int,int>>, comp> q;

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

	in >> n >> m;

	for (int i = 0 ; i < m ; i++) {

		int x, y, z;

		in >> x >> y >> z;

		graf[x].push_back(make_pair(y,z));

	}

	d[1] = 0;

	for (int i = 2 ; i <=n ; i++)
		d[i] = INF;
	
	q.push(make_pair(1,0));

	while(!q.empty()) {
		pair<int,int> node = q.top(); q.pop();
		if (d[node.first] < node.second)
			continue;
		
		for (pair<int,int> neigh : graf[node.first]) {
			if (d[neigh.first] > d[node.first] + neigh.second) {
				d[neigh.first] = d[node.first] + neigh.second;
				q.push(make_pair(neigh.first, d[neigh.first]));
			}
		}

	}
	
	for (int i = 2 ; i <=n ; i++)
		out << d[i] << " ";

	in.close();
	out.close();

	return 0;
}