#include<iostream.h>
#include<conio.h>
#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;
}

/*void drum(int i)
{
  if(ant[i]!=0)
  {
    drum(ant[i]);
    cout<<i<<" ";
  }
  else
    cout<<i<<" ";
}
*/
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++)
    {
     // cout<<"drumul minim de la "<<i0<<"  la  "<<i<<" este "<<d[i]<<" : ";
     // cout<<" trece prin ";
     if(d[i]!=0)
    // cout<<d[i]<<" ";
     g<<d[i]<<" ";
     // drum(i);
      //cout<<endl;
     }
    // getch();
    return 0;
}