#include <fstream>
#include <vector>

using namespace std;

#define N 50000
#define oo 1000000000

int d[N + 1];
int h[N + 1], ph[N + 1];
int lh, n, m;

vector<int> la[N];
vector<int> lc[N];

void citeste()
{
	ifstream fi("dijkstra.in");
	
	fi >> n >> m;
	
	int i, a, b, c;
	for(i = 0; i < m; ++i)
	{
		fi >> a >> b >> c;
		la[a].push_back(b);
		lc[a].push_back(c);
	}

	fi.close();
}

void init()
{
	for(int i = 1; i <= n; ++i) d[i] = oo;
	d[1] = 0;
}

void inter(int ia, int ib)
{
	int aux = h[ia];
	h[ia] = h[ib];
	h[ib] = aux;

	ph[h[ia]] = ia;
	ph[h[ib]] = ib;
}

void urca(int poz)
{
	if(poz == 1) return;
	int t = poz / 2;
	if(d[h[t]] < d[h[poz]]) return;
	inter(t, poz);
	urca(t);
}

void coboara(int poz)
{
	int idmin = poz;
	int f1 = 2 * poz, f2 = 2 * poz + 1;
	if(f1 <= lh) if(d[h[idmin]] > d[h[f1]]) idmin = f1;
	if(f2 <= lh) if(d[h[idmin]] > d[h[f2]]) idmin = f2;
	if(idmin == poz) return;
	inter(idmin, poz);
	coboara(idmin);
}

void scrie()
{
	ofstream fo("dijkstra.out");
	for(int i = 2; i <= n; ++i)
	{
		if(d[i] == oo) fo << "0 ";
		else fo << d[i] << " ";
	}
	fo << "\n";
	fo.close();
}

void adauga(int nod)
{
	lh++;
	h[lh] = nod;
	ph[nod] = lh;
	urca(lh);
}

void scoate_min()
{
	inter(1, lh);
	lh--;
	coboara(1);
}

void dijkstra()
{
	adauga(1);	
	int e, ne, nc, i;
	while(lh > 0)
	{
		e = h[1];
		scoate_min();
		for(i = 0; i < (int)la[e].size(); ++i)
		{
			ne = la[e][i];
			nc = lc[e][i];
			if(d[ne] > d[e] + nc)
			{
				d[ne] = d[e] + nc;
				adauga(ne);
			}
		}
	}
}

int main()
{
	citeste();	
	init();
	dijkstra();
	scrie();
	return 0;
}