#include <fstream>
#include <queue>
using namespace std;

struct	NOD{
	int	vf;
	int	cost;
	NOD	*next;
};

int	N, M;
NOD	*list[50000];
int	d[50001], viz[50001];
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int> > > vecini; 
int	inf = 1 << 30;

void	adaugare_muchie(int x, int y, int c)
{
	NOD *nod = new NOD;
	nod->vf = y;
	nod->cost = c;
	nod->next = list[x];
	list[x] = nod;
}

void	citire()
{
	ifstream fin("dijkstra.in");
	int x, y, c;

	fin >> N >> M;
	for (int i = 0; i < M; i++)
	{
		fin >> x >> y >> c;
		adaugare_muchie(x, y, c);
	}
	fin.close();
}

void	init()
{
	for (int i = 2; i <= N; i++)
		d[i] = inf;
}

void	dijkstra()
{
	NOD	*nod;
	int	v;

	vecini.push({0, 1});
	d[1] = 0;
	while (!vecini.empty())
	{
		v = vecini.top().second;
		vecini.pop();
		nod = list[v];
		while (nod)
		{
			if (!viz[nod->vf])
			{
				viz[nod->vf] = 1;
				vecini.push({nod->cost, nod->vf});
			}
			nod = nod->next;
		}
		nod = list[v];
		while (nod)
		{
			if (d[v] + nod->cost < d[nod->vf])
				d[nod->vf] = d[v] + nod->cost;
			nod = nod->next;
		}
	}
}

void	afisare()
{
	ofstream fout("dijkstra.out");

	for(int i = 2; i <= N; i++)
		if (d[i] == 1 << 30)	fout << '0' << ' ';
		else 			fout << d[i] << ' ';
	fout.close();
}

int	main(void)
{
	citire();
	init();
	dijkstra();
	afisare();
	return (0);
}