#include <fstream>

using namespace std;

#define tata(x) (x>>1)
#define st(x) (x<<1)
#define dr(x) ((x<<1)|1)

#define INF 1000000000

#define N 50001
#define M 250001

int h[N]; //heap
int poz[N];
int d[N]; //distanta de la nodul 1 la celelalte noduri
int lh; //dimensiune (lungime) heap
int n,m; 

struct arc
{
	int x,y,c;
};

arc w[M];
int nrv[N];
int *la[N], *lc[N];

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

inline void schimba(int ind_a, int ind_b)
{
	int aux = h[ind_a];
	h[ind_a] = h[ind_b];
	h[ind_b] = aux;

	poz[h[ind_a]] = ind_a;
	poz[h[ind_b]] = ind_b;
}

void coboara(int p)
{
	int id_max = p;
	if((st(p) <= lh) && (d[h[st(p)]] < d[h[id_max]])) id_max = st(p);
	if((dr(p) <= lh) && (d[h[dr(p)]] < d[h[id_max]])) id_max = dr(p);
	if(p != id_max)
	{
		schimba(p, id_max);
		coboara(id_max);
	}
}

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

void citeste() //citeste din fisier
{
	int x,y,c;
	ifstream fi("dijkstra.in");
	fi >> n >> m;
	int i;
	for(i=1;i<=m;++i)
	{
		fi >> x >> y >> c;
		w[i].x=x;
		nrv[x]++;
		w[i].y=y;
		w[i].c=c;
	}
	for(i=1;i<=n;++i) 
	{
		la[i]=new int[nrv[i] + 1];
		lc[i]=new int[nrv[i] + 1];
		la[i][0] = lc[i][0] = 0;
	}
	for(i=1;i<=m;++i)
	{
		la[w[i].x][++la[w[i].x][0]] = w[i].y;
		lc[w[i].x][++lc[w[i].x][0]] = w[i].c;
	}
	fi.close();
}
void dijkstra()
{
	int x,y;
	lh = 1;
	h[1] = 1;
	poz[1] = 1;
	int i;
	while(lh)
	{
		x = h[1];
		schimba(1,lh);
		--lh;
		coboara(1);
		for(i = 1; i <= nrv[x]; ++i)
		{
			y = la[x][i];
			if(d[y] > d[x] + lc[x][i])
			{
				d[y] = d[x] + lc[x][i];
				h[++lh] = y;
				poz[y] = lh;
				urca(poz[y]);
			}				
		}
	}
}

void scrie()
{
	ofstream fo("dijkstra.out");
	for(int i=2;i<=n;++i) fo << ((d[i]==INF)?(0):(d[i])) << " ";
	fo << "\n";
	fo.close();
}
int main()
{
	citeste();
	init_d();
	dijkstra();
	scrie();
	return 0;
}