// dijkstraTest.cpp : Defines the entry point for the console application.
//

//#include "stdafx.h"
#include <queue>
#include <vector>
#include <fstream>

struct nod{
	nod* urm;
	unsigned long vf, cost;
};

unsigned long n, m;

const unsigned long nmax = 50001;
const unsigned long maxUL = 4000000000;
nod* graf[nmax];
unsigned long d[nmax];
bool sel[nmax];

struct cmp
{
	bool operator()(std::pair<unsigned long, unsigned long> x, std::pair<unsigned long, unsigned long> y) { return x.first > y.first; };
};

void dijkstra()
{
	//auto cmp = [](std::pair<unsigned long, unsigned long> const & x, std::pair<unsigned long, unsigned long> const &y) { return x.first < y.first; };
	std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int>>, cmp> pq;
	pq.push(std::make_pair(0, 1));

	while (!pq.empty())
	{
		auto x = pq.top();
		pq.pop();
		nod* p = graf[x.second];
//		std::cout << "(" << x.first << " " << x.second << ")\n";
		while (p)
		{
			if (d[p->vf] > d[x.second] + p->cost)
			{
				d[p->vf] = d[x.second] + p->cost;
				pq.push(std::make_pair(d[p->vf], p->vf));
			}
			p = p->urm;
		}
		sel[x.second] = true;
	}
}

void load()
{
	std::ifstream fin("dijkstra.in");
	fin >> n >> m;
	for (unsigned int i = 0; i < m; i++)
	{
		unsigned long x, y, cost;
		fin >> x >> y >> cost;
		nod* v = new nod;
		v->urm = graf[x];
		v->vf = y;
		v->cost = cost;
		graf[x] = v;
	}
	for (unsigned int i = 2; i <= n; i++)
		d[i] = maxUL;
	fin.close();
}

void print()
{
	std::ofstream fout("dijkstra.out");
	for (unsigned int i = 2; i <= n; i++)
	{
		fout << (d[i] == maxUL ? 0 : d[i]) << " ";
	}
	fout.close();
}

int main()
{
	load();
	dijkstra();
	print();

    return 0;
}