#include<iostream.h>
#include<fstream.h>

int a[500][500], n,m,s[500],p[500],d[500];

ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
	

void afisare()
{
	int i,j;
	for(i=1;i<=n;i++)
	{
		for(j=1;j<=n;j++)
		{
			if(a[i][j]<10) g<<a[i][j]<<"    ";
			else if(a[i][j]<100) g<<a[i][j]<<"   ";
			         else if(a[i][j]<1000) g<<a[i][j]<<"  ";
							else g<<a[i][j]<<" ";
		}
	g<<endl;
	}
	
}


void dijkstra(int x)
{
	int i,j,min,y;
	s[x]=1;
	
	
	for(i=1;i<=n;i++)
	{
		d[i]=a[x][i];
		
	
	if(i!=x && d[i]<2000)
		p[i]=x;
	}
	
		
	for(i=1;i<=n-1;i++)
	{
		for(j=1,min=2000;j<=n;j++)
		
			if(s[j]==0 && d[j]<min)
			{
				min=d[j];
				y=j;
			}
			s[y]=1;
			
			for(j=1;j<=n;j++)
			{
				if(s[j]==0&& d[j]>d[y]+a[y][j])
				{
					d[j]=d[y]+a[y][j];
					p[j]=y;
				}
			}
		
	}
	
	
	
	
}



main()
{
	
	
 int i,x,y,p;

	
	f>>n>>m;
	
	
	for(i=1;i<=n;i++)
		for(x=1;x<=n;x++)
			a[i][x]=2000;
	
	for(i=1;i<=m;i++)
	{
		f>>x>>y>>p;
		a[x][y]=p;
	}
	
	
	

	
	dijkstra(1);
	
	for(i=2;i<=n;i++)
		g<<d[i]<<" ";
	

}