//---------------------------------------------------------------------------
#include <stdio.h>

const int MUCHO = 1000000;

void bpp(int *vertices,int origen, int destino,int *costos,int **w,int n)
  {
  int i;

  if( costos[origen] >= costos[destino] )
    return;

  for(i = 0; i < n; i++)
    {
    if( vertices[i] != 1 && w[origen][i] != MUCHO )
      {
      if( costos[origen] + w[origen][i] < costos[i] )
        {
        costos[i] = costos[origen] + w[origen][i];
        if( i != destino )
          {
          vertices[i] = 1;
          bpp(vertices,i,destino,costos,w,n);
          vertices[i] = 0;
          }
        }
      }
    }
  }
//---------------------------------------------------------------------------
int ** leeGrafoBidireccionado(FILE *input,int &n,int &m)
  {
  int **w,i,j,x,y,c;

  /// Leemos cuantos vértices y aristas tiene el grafo.
  fscanf(input,"%d %d",&n,&m);

  /// Pedimos memoria
  w = new int*[n];
  for(i = 0; i < n; i++)
    {
    w[i] = new int[n];

    /// Asignamos el valor de infinito a todas las aristas.
    for(j = 0; j < n; j++)
      w[i][j] = MUCHO;
    }

  /// Leemos las aristas
  for(i = 0; i < m; i++)
    {
    fscanf(input,"%d %d %d",&x,&y,&c);
    w[x][y] = c;
    w[y][x] = c;
    }

  return w;
  }
//---------------------------------------------------------------------------
int main(void)
  {
  FILE *input,*output;
  int i;
  int **w,*vertices,*costos,n,m,origen,destino;

  /// Leemos el archivo de entrada.
  if( (input=fopen("input_2_2_1.txt","r+t")) == NULL )
    return 0;

  /// Leemos los datos del grafo
  w = leeGrafoBidireccionado(input,n,m);

  /// Leeemos los dos datos extras (origen y destino)
  fscanf(input,"%d %d",&origen,&destino);

  /// Cerramos el archivo.
  fclose(input);

  /// Pedimos memoria para la lista de costos y de vértices visitados.
  costos = new int[n];
  vertices = new int[n];

  /// Inicializamos todos los vértices
  for(i = 0; i < n; i++)
    {
    vertices[i] = 0;
    costos[i] = MUCHO;
    }
  vertices[origen] = 1;
  costos[origen] = 0;

  /// Resolvemos
  bpp(vertices,origen,destino,costos,w,n);

  /// Abrimos el archivo para imprimir.
  if( (output=fopen("output_2_2_1.txt","w+t")) == NULL )
    return 0;

  fprintf(output,"%d",costos[destino]);

  /// Cerramos el archivo de salida
  fclose(output);

  /// Liberamos la memoria pedida.
  for(i = 0; i < n; i++)
    delete[] w[i];
  delete[] w;
  delete[] costos;
  delete[] vertices;

  return 0;
  }
//---------------------------------------------------------------------------