using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.IO;

namespace ConsoleApplication8
{
    class Program
    {
        public static int[] distmin;
        public static int[] tata;
        static void Main(string[] args)
        {
            StreamReader sr = new StreamReader("c:\\users\\ivn\\documents\\visual studio 2015\\Projects\\ConsoleApplication8\\ConsoleApplication8\\in.txt");
            //la asta fisierul e asa : prima linie numarul de teste,apoi pe urmatoare linie numarul de planete, numarul de legaturi intre ele, si apoi cele doua sate in care vrei sa afli distanta
            // apoi ai cate doua planete si ce cost este intre ele
            string[] nr = sr.ReadLine().Split(' ');
            int nrteste = Int32.Parse(nr[0]);
            for(int teste =0;teste<nrteste;teste++)
            {
                nr = sr.ReadLine().Split(' ');
                int n = Int32.Parse(nr[0]);
                int m = Int32.Parse(nr[1]);
                int nodStart = Int32.Parse(nr[2])-1;
                int nodFinal = Int32.Parse(nr[3])-1;
                int[,] c = new int[n, n];

                for(int i=0;i<n;i++)
                    for (int j = 0; j < n; j++)
                    {

                        c[i, j] = 99999;
                    }
                for (int j = 0; j < m; j++)
                {
                    nr = sr.ReadLine().Split(' ');
                    int x = Int32.Parse(nr[0])-1;
                    int y = Int32.Parse(nr[1])-1;
                    int cost = Int32.Parse(nr[2]);
                    c[x, y] = cost;
                    c[y, x] = cost;


                }





                int costmin;
                jack(c, nodStart, out distmin, out tata);
                AfiseazaDrum(nodStart, nodFinal, tata, c, out costmin);
                if (costmin == 199998)
                    costmin = 2000;
                Console.Write(costmin);
                Console.WriteLine();
            }
            Console.Read();
        }



        static void jack(int[,] c, int nod, out int[] distmin, out int[] tata)
        {

            int infinit = 99999;
            int n = c.GetLength(0);
            int[] vizitat = new int[n];
            Array.Clear(vizitat, 0, vizitat.Length);
            distmin = new int[n];
            tata = new int[n];


            for (int i = 0; i < n; i++)
            {
                distmin[i] = c[nod, i];
                tata[i] = (c[nod, i] == 99999 ? nod : -1);

            }

            tata[nod] = -1;
            vizitat[nod] = 1;

            for (int i = 0; i < n - 1; i++)
            {
                int min = int.MaxValue;
                int indexmin = -1;
                for (int j = 0; j < n; j++)
                {
                    if (vizitat[j] == 0)
                    {
                        if (min > distmin[j])
                        {
                            min = distmin[j];
                            indexmin = j;
                        }

                    }


                }
                vizitat[indexmin] = 1;


                for (int j = 0; j < n; j++)
                {
                    if (vizitat[j] == 0)
                    {
                        if (distmin[j] > distmin[indexmin] + c[indexmin, j])
                        {

                            distmin[j] = distmin[indexmin] + c[indexmin, j];
                            tata[j] = indexmin;
                        }

                    }
                }
            }
        }


        static List<int> AfiseazaDrum(int nodStart, int nodFinal, int[] tata, int[,]c, out int costmin)

        {
            List<int> drum = new List<int>();
            costmin = 0;
            int x = nodFinal;
            while(x!=-1)
            {
                drum.Add(x);
                x = tata[x];
            }
            drum.Reverse();
            foreach(int nod in drum)
            {

                costmin = costmin + Convert.ToInt32(c[nodStart, nod] == 9999 ? nod : c[nodStart, nod]);
                nodStart = nod;
            }
            return drum;


        }




        }
    }