// Coada de prioritati are O(n) pentru aflarea maximului si O(1) pentru update_key
#include<fstream>
#include<iostream>
#include<vector>
#include<algorithm>
#include<utility>
#define INF 2147483647
using namespace std;

vector < pair <int, int> > *adj; // lista de adiacenta
vector<int> dist;
vector<int> parent;
vector<int> visited;
int n, m, u, v, c, i, j, visitedElem;

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

void relax(int u, int v)
{
	if(dist[adj[u][v].first] > dist[u] + adj[u][v].second)
		dist[adj[u][v].first] = dist[u] + adj[u][v].second;
	parent[adj[u][v].first] = u;
}

int min(vector<int> dist)
{
	int min, pozMin;
	i = 0;
	// while-ul se opreste la primul element nevizitat. Pe acela il vom considera primul minim
	while(i < n && visited[i] == 1)
		i++;
	pozMin = i;
	min = dist[i];
	for( ; i < n; i++)
	{
		if(min > dist[i] && visited[i] == 0)
		{
			min = dist[i];
			pozMin = i;
		}
	}
	return pozMin;
}
			

void Dijkstra()
{
	while(visitedElem < n)
	{
		u = min(dist);
		visited[u] = 1;
		visitedElem++;
		for(i = 0; i < (int)adj[u].size(); i++) 
			if(!visited[adj[u][i].first])
				relax(u, i);
	}
}

int main()
{
	ifstream fin("dijkstra.in");
	ofstream fout("dijkstra.out");
	fin >> n >> m;
	adj = new vector< pair < int, int > >[n];
	dist.resize(n);
	visited.resize(n);
	parent.resize(n);
	for(i = 0; i < m; i++)
	{
		fin >> u >> v >> c;
		u--; v--; // retinem nodurile de la 0 la n - 1
		adj[u].push_back(make_pair(v, c));
	}
	init(0);
	Dijkstra();
	for(i = 1; i < n; i++)
		fout << dist[i] << " ";
	return 0;
}