#include<fstream>
#include<iostream>
#include<vector>
#include<algorithm>
#include<utility>
#define INF 2147483647
using namespace std;

vector < pair <int, int> > *adj; // lista de adiacenta
struct Nod {
	int n, dist;
};
vector<Nod> q; // heap cu distantele de la sursa la fiecare nod
vector<int> s;
int parent[50000];
int n, m, i, j, c, u, v;

void init(int s)
{
	for(i = 0; i < n; i++)
	{
		q[i].n = i;
		q[i].dist = INF;
		parent[i] = -1;
	}
	q[s].dist = 0;
}	

bool comp(Nod a, Nod b)
{
	if(a.dist > b.dist)
		return true;
	return false;
}

int main() 
{
	ifstream fin("dijkstra.in");
	ofstream fout("dijkstra.out");
	fin >> n >> m;
	adj = new vector< pair <int, int> >[n]; 
	q.resize(n);
	s.resize(n);
	// Citim muchiile si le adaugam in lista de adiacenta
	for(i = 0; i < m; i++)
	{
		fin >> u >> v >> c;
		u--; v--;
		adj[u].push_back(make_pair(v, c));
	}
	// Initializam vectorii dist si parent
	init(0);
	make_heap(q.begin(), q.end(), comp);
	while(q.size() > 0)
	{
		pop_heap(q.begin(), q.end(), comp);
		Nod u = q.back();
		q.pop_back();
		s[u.n] = u.dist;
		for(i = 0; i < (int)adj[u.n].size(); i++)
		{
			int v = adj[u.n][i].first; // unul dintre vecinii lui u (foarte probabil are dist INF)
			for(j = 0; j < (int)q.size(); j++) // il cautam in heap
			{
				if(q[j].n == v) 
				{
					if(q[j].dist > u.dist + adj[u.n][i].second) // daca distanta pana la el e mai mare decat ar fi prin u
					{
						q[j].dist = u.dist + adj[u.n][i].second;
					}
					break;
				}
			}
		}
		make_heap(q.begin(), q.end(), comp);
	}
	for(i = 1; i < n; i++)
	{
		 fout << s[i] << " ";
	}
	return 0;
}