#include<stdio.h>
#include<stdlib.h>
#include<conio.h>
#define pinf 20000000 //pentru plus infinit, o valoare mare care nu exista

int a[20][20],n,m;

void citire_cost(int *t, int *v)
{
    FILE *f;
    int i,j,c,x,y;
    f= fopen("roy_in.txt","r");

    fscanf(f,"%d",&n);
    fscanf(f,"%d",&m);
    fscanf(f,"%d%d",t,v);
//initializare matrice
for(i=1;i<=n;i++)
    for(j=1;j<=n;j++)
        if(i==j)
            a[i][j]=0;
        else
            a[i][j]=pinf;
    for(i=1;i<=m;i++)
    {
        fscanf(f,"%d %d %d",&x,&y,&c);
        a[x][y]=a[y][x]=c;
    }

    fclose(f);
}

void RoyFloyd() // roy floyd
{
    int i,j,k;
    for(k=1;k<=n;k++)
        for(i=1;i<=n;i++)
            for(j=1;j<=n;j++)
                if(a[i][j]>a[i][k]+a[k][j])
                        {
                            a[i][j]=a[i][k]+a[k][j];
                        }
}
void scriu_drum(int nod_initial,int nod_final) // functia primeste ca parametri cele doua noduri pt care se determina optimul
{
    if(a[nod_initial][nod_final]<pinf)
        {
            printf("%d",a[nod_initial][nod_final]);
        }
}
void main()
{
    int x,y;
    citire_cost(&x,&y);
    RoyFloyd();
    scriu_drum(x,y);
   // _getch();
}