#include<fstream.h>
long c[120][120],n,s[120],ant[120],d[120],i,j,k,pas,min,i0,m;
const infinit=90000;
void citire()
{
  int i,j,k;
  ifstream f("dijkstra.in");
  f>>n>>m;

  for(i=1;i<=n;i++)
    for(j=1;j<=m;j++)
      if(i==j)
	c[i][j]=0;
      else
	c[i][j]=infinit;
      while(f>>i>>j>>k)

	c[i][j]=k;
}


int  main()
{

  citire();
  ofstream g("dijkstra.out");
 
 i0=1;
  for(i=1;i<=n;i++)
  {
    s[i]=0;
    d[i]=c[i0][i];
    if(d[i]<infinit)
      ant[i]=i0;
    else
      ant[i]=0;
  }
  s[i0]=1;
  ant[i0]=0;
  for(pas=1;pas<n;pas++)
  {
    min=infinit;
    for(i=1;i<=n;i++)
      if(!s[i]&&d[i]<min)
      {
	min=d[i];
	k=i;
      }
      s[k]=1;
      for(i=1;i<=n;i++)
	if(!s[i]&&d[i]>d[k]+c[k][i])
	{
	  d[i]=d[k]+c[k][i];
	  ant[i]=k;
	}
    }
    for(i=1;i<=n;i++)
    {
          if(d[i]!=0)
         g<<d[i]<<" ";
     
     }
    
    return 0;
}