#include <iostream>
#include <fstream>
#include <vector>
#include <set>
using namespace std;
ifstream dijstra_in("dijkstra.in");
ofstream dijstra_out("dijkstra.out");

struct edge{
	int distanta;
	int nod;
};

set<pair<int, int> > coada;
vector<int> dis;
vector<vector<edge> > graph;
int n, m;
int x, y, z;

void citire()
{
	edge aux;
	dijstra_in >> n >> m;
	graph.resize(n + 1);
	dis.resize(n + 1, 100000000);
	for (int i = 1; i <= m; i++)
	{
		dijstra_in >> x >> y >> z;
		aux.nod = y;
		aux.distanta = z;
		graph[x].push_back(aux);
	}
}
void calcul_drum(int start)
{
	int i;
	dis[start] = 0;
	int curent, drum;
	coada.insert(make_pair(0, start));
	while (coada.size()>0)
	{
		drum = (*coada.begin()).first;
		curent = (*coada.begin()).second;
		coada.erase(coada.begin());
		for (i = 0; i<graph[curent].size(); i++)
		{
			if (dis[graph[curent][i].nod]>drum + graph[curent][i].distanta)
			{
				dis[graph[curent][i].nod] = drum + graph[curent][i].distanta;
				coada.insert(make_pair(drum + graph[curent][i].distanta, graph[curent][i].nod));
			}
		}

	}
}
int main()
{
	citire();
	calcul_drum(1);
	for (int i = 2; i <= n; i++)
	{
		if (dis[i] != 100000000)
			dijstra_out << dis[i] << " ";
		else
			dijstra_out << 0 << " ";
	}
}