#include <iostream>
#include <set>
#include <vector>
#include <fstream>
#include <algorithm>
#include <utility>
#include <limits.h>

using namespace std;

#define Inf INT_MAX
#define NMax 50002

typedef set<pair<int, int> > dijkstra_set;

int n, m, d[NMax];
vector<pair<int, int> > v[NMax];
dijkstra_set st;

void dijkstra (int nod)
{
	st.clear ();

	// Reset all nodes
	for (int i = 0; i <= n; i++)
		d[i] = Inf;	
	
	// Add starting node to queue
	d[nod] = 0;
	st.insert(make_pair(0, nod));
	
	while (!st.empty ()) {
		nod = st.begin()->second;
		st.erase(st.begin());
		// Check all neighbours
		for (int i = 0; i < v[nod].size (); i++) {
			int next = v[nod][i].first;
			int dist = d[nod] + v[nod][i].second;
			
			//cout << "Link " << nod << " " << next << " " << dist << '\n';			

			if (dist < d[next]) {
				// Next node is better -> add to queue
				pair<int, int> p = make_pair (d[next], next);
				dijkstra_set::iterator it = st.find(p);
				if (it != st.end ()) {
					//remove from queue so we can reinsert
					st.erase(it);
				}
				
				// insert
				d[next] = dist;
				st.insert (make_pair (d[next], next));
			}
		}
		/*for (int i = 2; i <= n; i++) {
			cout << d[i] << " ";
		}
		cout << '\n';*/
	}
}

int main ()
{
	ifstream fin ("dijkstra.in");
	ofstream fout ("dijkstra.out");
	
	fin >> n >> m;
	for (int i = 0; i < m; i++) {
		int x, y, z;
		fin >> x >> y >> z;
		v[x].push_back(make_pair(y, z));
		//v[y].push_back(make_pair(y, z));
	}
	
	dijkstra(1);
	for (int i = 2; i <= n; i++) {
		fout << d[i] << " ";
	}

	fout.flush();

	return 0;
}