/*

    LibreOJ #119. 最短路 

    堆优化的Dijkstra

*/

#include <cstring>

#include <cstdio>

#include <queue>

#define Max 6000

void read (int &now)

{

    now = ;

    register char word = getchar ();

    while (word < '' || word > '')

        word = getchar ();

    while (word >= '' && word <= '')

    {

        now = now *  + word - '';

        word = getchar ();

    }

}

struct Data

{

    int Id;

    int dis;

    bool operator < (const Data &now) const

    {

        return this->dis > now.dis;

    }

    Data (int __Id, int __dis) : Id (__Id), dis (__dis) {};

    Data () {};

};

class Dijkstra_Type

{

    private :

        int __to[Max << ], __next[Max << ];

        int __dis[Max << ];

        int Edge_Count;

        int edge_list[Max];

        bool visit[Max];

        int dis[Max];

    public :

        void Insert_edge (int from, int to, int dis)

        {

            Edge_Count ++;

            __to[Edge_Count] = to;

            __next[Edge_Count] = edge_list[from];

            edge_list[from] = Edge_Count;

            Edge_Count ++;

            __to[Edge_Count] = from;

            __next[Edge_Count] = edge_list[to];

            edge_list[to] = Edge_Count;

            __dis[Edge_Count] = __dis[Edge_Count - ] = dis;

        }

        int Dijkstra (int Start, int End)

        {

            std :: priority_queue <Data> Queue;

            memset (dis, 0x3f, sizeof dis);

            Data now ;

            for (Queue.push (Data (Start, )), dis[Start] = ; !Queue.empty (); Queue.pop ())

            {

                now = Queue.top ();

                if (visit[now.Id])

                    continue;

                visit[now.Id] = true;

                for (int i = edge_list[now.Id]; i; i = __next[i])

                    if (dis[__to[i]] > dis[now.Id] + __dis[i])

                    {

                        dis[__to[i]] = dis[now.Id] + __dis[i];

                        Queue.push (Data (__to[i], dis[__to[i]]));

                    }

            }

            return dis[End];

        }

};

Dijkstra_Type Make;

int main (int argc, char *argv[])

{

    int N, M;

    int x, y, z;

    int S, T;

    for (read (N), read (M), read (S), read (T); M --; )

    {

        read (x);

        read (y);

        read (z);

        Make.Insert_edge (x, y, z);

    }

    printf ("%d", Make.Dijkstra (S, T));

    return ;

}