#include <stdio.h>
#include <stdlib.h>
#include <string.h>


//declararea constantelor


const int MAX_INT=0x7f7f7f7f/2;


//declararea variabilelor
int   noduri;
int   muchii;
int   v[100][100];
int   sel[100];
//int   par[100];
int   dist[100];

//declararea functiilor
void citire();
void afisare();
void dijkstra(int nod);

int main()
{
	memset(dist,0x7f,100*sizeof(int));
	citire();

  dijkstra(1);

  afisare();
	return 0;
}


void dijkstra(int nod)
{
  sel[nod]=true;
  if(dist[nod]>=MAX_INT)
  	dist[nod]=0;
    
  int Nod_Nou;
  int Dist_Nod_Nou;
  int i;

  do
  {
  	Nod_Nou=0;
    Dist_Nod_Nou=MAX_INT;

    //daca nu e acelasi nod, daca exista drum si daca nu a fost selectat
    for(i=1; i<=noduri; i++)
    {
    	if(i!=nod && sel[i]==false && v[nod][i]>0)
      {
      	//verificam daca noul drum nu e mai mic decat celalalt
        if(dist[i]> dist[nod]+v[nod][i])
        {
        	dist[i]=dist[nod]+v[nod][i];
        }
        if(Dist_Nod_Nou>dist[i])
        {
          Dist_Nod_Nou=dist[i];
          Nod_Nou=i;
        }
      }
    }
    if(Nod_Nou!=0)
    	dijkstra(Nod_Nou);

  }while(Nod_Nou);


}


void citire()
{
	FILE   *f;
  int     i;
  int     x,y,z;
	f=fopen("dijkstra.in","r");
  fscanf(f,"%d %d",&noduri,&muchii);
  for(i=1; i<=muchii; i++)
  {
  	fscanf(f,"%d %d %d",&x,&y,&z);
    v[x][y]=z;
    v[y][x]=z;
  }
  fclose(f);
}

void afisare()
{
	FILE *f;
  int   i;

  f=fopen("dijkstra.out","w");

  for(i=2; i<=noduri; i++)
  	fprintf(f,"%d ",dist[i]);

  fclose(f);
}