#include<fstream>
#include<iostream>
using namespace std;
typedef struct nod{int vec,l;nod *urm;}NOD;
NOD *p;
typedef struct {NOD *prim;}EXPERIMENT;
EXPERIMENT v[50001];
int marc[50001],d[50001];
int arc(int x,int i)
{
for(p=v[x].prim;p;p=p->urm)
	if(p->vec==i)return p->l;
return 999999;
}
int main ()
{
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
int i,n,j,l,min,poz,marcate=0,m;
f>>n>>m;
m=n+1;
while(f>>i>>j>>l)
	{
	p=new NOD;
	p->vec=j;
	p->l=l;
	p->urm=v[i].prim;
	v[i].prim=p;
	d[--m]=999999;
	}
for(;m>=1;m--)
	if(!d[m])d[m]=999999;
for(p=v[1].prim;p;p=p->urm)
	d[p->vec]=p->l;
d[1]=0;
marc[1]=1;marcate++;
while(marcate!=n-1)
{
	min=999999;poz=0;
	for(i=2;i<=n;i++)
		if(marc[i]==0 and d[i]<min){min=d[i];poz=i;}
	marc[poz]=1;
	marcate++;
	for(i=2;i<=n;i++)
	{
	m=arc(poz,i);
		if(d[poz]+m<d[i])
			{
			d[i]=d[poz]+m;
			}
	}
}
for(i=2;i<=n;i++)
	if(d[i]==999999)g<<"0 ";
	else g<<d[i]<<" ";
g<<"\n";
f.close();
g.close();
return 0;
}