#include <fstream>
#include<iostream>
#define MAX 10000


using namespace std;
int mat[100][100];

 ifstream fin("sate.in");
 ofstream fout("sate.out");

void dijkstra(int start,int final,int n)
{
    int i, j, min, k, ok;
    int viz[MAX], d[MAX], tata[MAX];
    for (i = 1; i<=n; i++) {
        d[i] = mat[start][i];
        tata[i] = start;
        viz[i] = 0;
    }
    tata[start] = 0;
    viz[start] = 1;
    ok = 1;
    while (ok)
    {
        min = MAX;
        for (i = 1; i<=n; i++)
            if (!viz[i] && min>d[i])
            {
                min = d[i];
                k = i;
            }
        if (min != MAX)
        {
            viz[k] = 1;
            for (i = 1; i<=n; i++)
               if (!viz[i] && d[i]>d[k]+mat[k][i])
               {
                   d[i] = d[k]+mat[k][i];
                   tata[i] = k;
               }
        }
        else ok = 0;
    }
    if(d[final]!=0)
        cout<<"distanta minima este: "<<d[final];
    else
        cout<<"drumul nu exista";

}

int main()
{
    int nSate,nMuchii,nStart,nFinal,i,j,a,b,x;


    fin>>nSate;
    cout<<"numar sate: "<<nSate<<endl;

    fin>>nMuchii;
    cout<<"numar legaturi: "<<nMuchii<<endl;

    fin>>nStart;
    cout<<"nodul de start este: "<<nStart<<endl;

    fin>>nFinal;
    cout<<"nodul final este: "<<nFinal<<endl;

    for(i=1;i<=nSate;i++)
        for(j=1;j<=nSate;j++)
            mat[i][j]=MAX;

    for(i=1;i<=nMuchii;i++)
    {
        fin>>a>>b;
        fin>>x;
        mat[a][b]=mat[b][a]=x;
    }

    dijkstra(nStart,nFinal,nSate);
    return 0;

}