// Dijkstra cu Arbori de intervale
using namespace std;
#include <cstdio>
#include <string>
#include <fstream>
#define N 50001
#define common \
	int m=(l+r)>>1, L=n<<1, R=L|1
#define oo 0x3f3f3f3f
#define dim 8192

char ax[dim];
int pz;

inline void cit(int &x)
{
	x=0;
	while(ax[pz] <'0' || ax[pz] > '9')
		if(++pz == dim) fread(ax,1,dim,stdin),pz=0;
	while(ax[pz] >= '0' && ax[pz] <= '9')
	{
		x=x*10+ax[pz]-'0';
		if(++pz == dim ) fread(ax,1,dim,stdin),pz=0;
	}
}

struct nod { int x, c;nod*n;};

nod *a[N];

int H[(1<<17)+1], poz[(1<<17)+1];
int d[N];

int n, m;

void update(int n, int l, int r, int p, int v)
{
	if(l >= r) {H[n]=v;poz[n]=l; return;}

	common;

	if(p <= m) update(L, l, m, p, v);
	else       update(R, m+1, r, p, v);

	if(H[L] < H[R]) H[n]=H[L], poz[n]=poz[L];
	else H[n]=H[R], poz[n]=poz[R];
}

void dijkstra()
{
	int i;

	memset(d, oo, sizeof(d));
	d[1]=0;
	for(i=1; i <= n; ++i) update(1,1, n, i, d[i]);

	int nn=n,u;
	nod *it;

	while(nn--)
	{
		u=poz[1];

		update(1,1,n, u, oo);

		for(it=a[u]; it ; it=it->n)
			if(d[u] + it->c < d[it->x])
			{
				d[it->x]=d[u] + it->c;
				update(1, 1, n, it->x, d[it->x]);
			}
	}

	ofstream g("dijkstra.out");
	for(i=2; i <= n; ++i) g<<(d[i] == oo ? 0 : d[i])<<" ";
}

void read()
{
	ifstream fin("dijkstra.in");
	fin>>n;
	fin>>m;
	int p, q, c;
	nod *t;
	while(m--)
	{
    fin>>p;
    fin>>q;
	fin>>c;
		t=new nod;
		t->x=q;
		t->c=c;
		t->n=a[p];
		a[p]=t;
	}
}

int main()
{
	read();
	dijkstra();


	return 0;
}