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

//#include "stdafx.h"
#include <stdio.h>
#include <queue>
#include <vector>
//#include <iostream>

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()
{
	FILE *in = fopen("dijkstra.in", "r");
	fscanf(in, "%lu %lu", &n, &m);
	for (unsigned int i = 0; i < m; i++)
	{
		unsigned long x, y, cost;
		fscanf(in, "%lu %lu %lu", &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;
	fclose(in);
}

void print()
{
	FILE *out = fopen("dijkstra.out", "w");
	for (unsigned int i = 2; i <= n; i++)
	{
		fprintf(out, "%lu ", d[i] == maxUL ? 0 : d[i]);
	}
	fclose(out);
}

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

    return 0;
}