#include<fstream.h>
int legaturi[1000][1000][2],distanta[1000],n,sel[1000];
int minim_neselectat ()
{
  int j=1,k;
  while(sel[j]==1)
    j++;
  for (k=j+1;k<=n;k++)
  {
    if (sel[k]==0 && distanta[k]<distanta[j])
      j=k;
  }
  return j;
}
void Dijkstra (int i)
{
  int j,k;
  sel[i]=1;
  for (j=1;j<=legaturi[i][0][0];j++)
  {
    if (distanta[legaturi[i][j][0]]>(distanta[i]+legaturi[i][j][1]))
      distanta[legaturi[i][j][0]]=distanta[i]+legaturi[i][j][1];
  }
  k=minim_neselectat();
  if (k!=n+1)
  {
    Dijkstra (k);
  }
}
int main ()
{
  int i,j,k;
  ifstream f ("dijkstra.in");
  ofstream g ("dijkstra.out");
  f>>n;
  f>>i;
  while (f>>i>>j>>k)
  {
	legaturi[i][0][0]++;
    legaturi[i][legaturi[i][0][0]][0]=j;
    legaturi[i][legaturi[i][0][0]][1]=k;
  }
  for(i=1;i<=n;i++)
  {
    distanta[i]=200000;
  }
  distanta[1]=0;
  Dijkstra (1);
  for (i=2;i<=n;i++)
  {
	  if (distanta[i]==200000)
	  {
		  distanta[i]=0;
	  }
	  g<<distanta[i]<<" ";
  }
  f.close();
  g.close();
  return 0;
}