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

ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
const int Nmax=50001;
const int INF= (1 << 30) - 1;
int N, M;
int A, B, C;
int h[Nmax], d[Nmax], p[Nmax];

struct muchie { int y; int cost; };
vector <muchie> v[Nmax];
muchie aux;
int nh;
void citire()
{
	f >> N >> M;
	for(int i = 1; i <= M; i ++)
	{
		f >> A >> B >> C;
		aux.y = B;
		aux.cost = C;
		v[A].push_back(aux);
	}
}

inline int tata(int nod) { return nod/2; }
inline int fiu_stanga(int nod) { return nod*2; }
inline int fiu_dreapta(int nod) { return nod*2+1; }

void schimba(int x, int y)
{
	int aux;
	aux = h[x];
	h[x] = h[y];
	h[y] = aux;
	p[h[x]] = x;
	p[h[y]] = y;
}

void coboara(int x)
{
	int bun;
	bun = x;
	if(fiu_stanga(x) <= nh && d[h[fiu_stanga(x)]] < d[h[bun]]) bun = fiu_stanga(x);
	if(fiu_dreapta(x) <= nh && d[h[fiu_dreapta(x)]] < d[h[bun]]) bun = fiu_dreapta(x);
	
	if(bun != x)
	{
		schimba(bun, x);
		coboara(bun);
	}
}

void urca(int x)
{
	if(x > 1 && d[h[tata(x)]] > d[h[x]])
	{
		schimba(tata(x), x);
		urca(tata(x));
	}
}

void adauga(int x)
{
	h[++ nh] = x;
	p[h[nh]]=nh;
	urca(nh);
}

void sterge(int x)
{
	schimba(x, nh);
	nh--;
	
	coboara(x);
	urca(x);
}


void dijkstra(int x)
{
	for(int i = 1; i <= N; i ++) d[i] = INF; d[x] = 0;
	nh = 0;
	adauga(x);
	while(nh != 0)
	{
		x=h[1];
		sterge(1);
		for(size_t i = 0; i < v[x].size(); i ++)
		{
			int y, cost;
			y = v[x][i].y;
			cost = v[x][i].cost;
			if(d[x] + cost < d[y])
			{
				d[y] = d[x] + cost;
				if(p[y] == 0)
					adauga(y);
				else
					urca(p[y]);
			}
		}
	}
}

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

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