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

const int N = 50001;
const int INF = 2000000000;

struct destinatie
{
	int nod_dest, cost;
};

vector<destinatie> vecin[N]; int n;
int d[N];
bool vizitat[N]; int nevizitate;

//pair <dist, poz>
priority_queue< pair <int, int>, vector < pair <int, int> >, greater < pair <int, int> > > heap;

ifstream in("dijkstra.in");
ofstream out("dijkstra.out");

void citire()
{
	int m,a,b,c;
	destinatie dest;
	in>>n>>m;
	for (int i = 1; i <= m; ++i)
	{
		in>>a>>b>>c;
		dest.nod_dest = b;
		dest.cost = c;
		vecin[a].push_back(dest);
	}
}

void initializare_dijkstra()
{
	d[1] = 0;
	for (int i = 2; i <= n; ++i)
		d[i] = INF;
}

void dijkstra()
{
	int nod,dest,dist;
	initializare_dijkstra();
	vizitat[1] = true;//obicei bun, dar nu conteaza f mult ca oricum sunt dist pozitive.
	nevizitate = n-1;
	heap.push(make_pair (0,1));
	while (nevizitate > 0)
	{
		while (!heap.empty() && vizitat[heap.top().second])
			heap.pop();
		nod = heap.top().second;
		for (unsigned int i = 0; i < vecin[nod].size(); ++i)
		{
			dest = vecin[nod][i].nod_dest;
			dist = d[nod] + vecin[nod][i].cost;
			if (dist < d[dest])
			{
				d[dest] = dist;
				heap.push(make_pair (dist, dest));
			}
		}
		vizitat[nod] = true;
		--nevizitate;
	}
}

void afisare()
{
	for (int i = 2; i <= n; ++i)
		if (d[i] != INF)
			out<<d[i]<<' ';
		else
			out<<0<<' ';
}

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