#include<stdio.h>
const int pinfinit=36000;
int ret,a[200][200],i,j,n,k,m,poz,s[100],t[200],d[200],r,min;
FILE *f;
FILE *g;
void citire_graf()
{
	int x,y,z;
f=fopen("dijkstra.in","r");
g=fopen("dijkstra.out","w");
ret=fscanf(f,"%d%d",&n,&k);

for(i=0;i<=n;i++)
	for(j=0;j<=n;j++)
		if(i!=j)
		a[i][j]=pinfinit;
		else
			a[i][j]=0;

for(i=0;i<k;i++)
	{
		ret=fscanf(f,"%d%d%d",&x,&y,&z);
		a[x][y]=z;
		
	}

}


void drum(int i)
{
if (t[i]!=0) drum(t[i]);
printf(" %d ",i);
}

int main()
{
citire_graf();
r=1;
s[r]=1;
for(i=1;i<=n;i++)
	{
		d[i]=a[r][i];
		if(i!=r)
		if(d[i]<pinfinit) t[i]=r;
	}

for(i=1;i<=n-1;i++)
	{
		min=pinfinit;
		for(j=1;j<=n;j++)
			if(s[j]==0)
				if(d[j]<min)
				{
					min=d[j];
					poz=j;
				}
	s[poz]=1;
	for(j=1;j<=n;j++)
		if(d[j]>d[poz]+a[poz][j])
		{
			d[j]=d[poz]+a[poz][j];
			t[j]=poz;
		}
	}
	
for(i=1;i<=n;i++)
	if(i!=r)
	if(t[i]!=0)
	fprintf(g,"%d ",d[i]);
return 0;
}