#include<cstdio>
#define inf (1<<29)
using namespace std;
struct Nod {
	        int nod,c;
	        Nod *urm;
           }*g[50001];
int m,n,i,j,k,x,y,c,h[50001],d[50001],t[50001],poz[50001],nod;
void swap(int i,int j)
{
int x;
x=h[i];
h[i]=h[j];
h[j]=x;
x=poz[h[i]];
poz[h[i]]=poz[h[j]];
poz[h[j]]=x;
}
void heapup(int i)
{
if (d[h[i/2]]<d[h[i]]) return;
swap(i,i/2);
heapup(i/2);
}
void heapdown(int i)
{
int st,dr;
if (i*2>m) return;
st=d[h[i*2]];
if(i*2+1<=m)dr=d[h[i*2+1]];else dr=st+1;
if(st<dr)
	{
	 if(d[h[i]]<=st)return;
	 swap(i,2*i);
	 heapdown(i*2);
	}
else
	{
	if(d[h[i]]<=dr)return;
	swap(i,2*i+1);
	heapdown(2*i+1);
	}
}
int main()
{
Nod *p;
freopen("dijkstra.in","r",stdin);
freopen("dijkstra.out","w",stdout);
scanf("%d%d",&n,&m);
while (m--)
	{
	scanf("%d%d%d",&x,&y,&c);
	p=new Nod;
	p->c=c;p->nod=y;p->urm=g[x];g[x]=p;
	}
for(i=1;i<=n;i++)
    {
	d[i]=inf;
	h[i]=i;
	poz[i]=i;
	}
m=n;
d[1]=0;d[0]=-1;
for(i=0;i<n;i++)
	{
	nod=h[1];
	swap(1,m);
	m--;
	heapdown(1);
	for(p=g[nod];p!=NULL;p=p->urm)
		if(d[p->nod]>d[nod]+p->c)
    		{
			d[p->nod]=d[nod]+p->c;
			t[p->nod]=nod;
			heapup(poz[p->nod]);
	    	}
	}
for (i=2;i<=n;i++)
printf("%d ",d[i]);
	return 0;
}