#include <iostream>
#include <fstream>
#include <cstring>
#include <vector>
#include <set>
using namespace std;
#define oo 1000000000
ifstream in ("dijkstra.in");
ofstream out ("dijkstra.out");
int n, m;
vector <pair <int, int> > v[100001];
bool viz[100001];
int cost[100001];
void dij (int start)
{
	set <pair <int, int> >seti;
	seti.insert ({0, start});
	cost[start] = 0;
	while (!seti.empty())
	{
		int nod = seti.begin() -> second;
		int value = seti.begin() -> first;
		seti.erase(seti.begin());
		for (auto vecin:v[nod])
		{
			if (value + vecin.second < cost[vecin.first])
			{
				if (cost[vecin.first] != oo)
					seti.erase(seti.find({cost[vecin.first], vecin.first}));
				cost[vecin.first] = value + vecin.second;
				seti.insert({cost[vecin.first], vecin.first});
			}	
		}
	}
}
int main ()
{
	in >> n >> m;
	for (int i = 1;i<=m;++i)
	{
		int a, b, c;
		in >> a >> b >> c;
		v[a].push_back({b, c});
	}
	for (int i = 1;i<=n;++i)
		cost[i] = oo;
	dij(1);
	for (int i = 2;i<=n;++i)
		out << cost[i] << ' ';
	return 0;
}