#include<stdio.h>
#define N 50001
#define M 250001
#define oo 2000000
int n,m,d[N],*a[N],*a1[N],h[M],p[N],nh;
bool sel[N];
char s[50];
struct consturi{int x,y,z;}c[M];
void parsare(int k)
{
	int nr=0,num=0;
	for (int i=0; s[i]&&s[i]!=10; ++i)
	{
		while (s[i]>='0'&&s[i]<='9'&&s[i]&&s[i]!=10)
		{
			nr=nr*10+s[i]-'0';
			++i;
		}
		++num;
		if (num==1) c[k].x=nr;
		else
			if (num==2) c[k].y=nr;
		else
			if (num==3) c[k].z=nr;
		nr=0;
	}
}
void citire()
{
	freopen("dijkstra.in","r",stdin);
	freopen("dijkstra.out","w",stdout);
	scanf("%d%d\n",&n,&m);
	for (int i=1; i<=m; ++i)
	{
		gets(s);
		parsare(i);
		h[i]=i;
		++d[c[i].x];
	}
	for (int i=1; i<=n; ++i)
	{
		a[i]=new int [1+d[i]];
		a[i][0]=0;
		a1[i]=new int [1+d[i]];
		a1[i][0]=0;
	}
	for (int i=1; i<=m; ++i)
	{
		a[c[i].x][++a[c[i].x][0]]=c[i].y;
		a1[c[i].x][++a1[c[i].x][0]]=c[i].z;
	}
}

inline void schimb(int &x,int &y)
{
	int aux=x;
	x=y;
	y=aux;
}

void coboara(int p)
{
	int pmin=p;
	if(2*p<=nh && d[h[2*p]] < d[h[pmin]])
		pmin=2*p;
	if(2*p+1<=nh && d[h[2*p+1]] < d[h[pmin]])
		pmin=2*p+1;
	if(pmin!=p)
	{
		schimb(h[p],h[pmin]);
		coboara(pmin);
	}
}

void urca(int p)
{
	while(p>=2 && d[h[p/2]] > d[h[p]])
	{
		schimb(h[p],h[p/2]);
		p/=2;
	}
}

int minim()
{
	/*int min=oo,pmin=-1;
	for (int i=1; i<=n; ++i)
	{
		if (!sel[i] && d[i]<min)
		{
			min=d[i];
			pmin=i;
		}
	}
	return pmin;*/
	while(nh && sel[h[1]])
	{
		schimb(h[1],h[nh--]);
		if(!sel[h[1]])
			coboara(1);
	}
	if(nh==0)
		return -1;
	return h[1];
}
void update(int x)
{
	for (int i=1; i<=a[x][0]; ++i)
	{
		int y=a[x][i],c=a1[x][i];
		if (d[x]+c<d[y])
		{
			d[y]=d[x]+c;
			h[++nh]=y;
			urca(nh);
		}
	}
}
void dijkstra(int x0)
{
	for (int i=1; i<=n; ++i)
	{
		d[i]=oo;
		sel[i]=false;
	}
	d[x0]=0;
	h[++nh]=x0;
	for (int i=1; i<n; ++i)
	{
		int x=minim();
		if(x==-1)
			return;
		sel[x]=true;
		update(x);
	}
}
void afis()
{
	for (int i=2; i<=n; ++i)
		if (d[i]!=oo)
			printf("%d ",d[i]);
		else
			printf("0 ");
}
int main()
{
	citire();
	dijkstra(1);
	afis();
	return 0;
}