// Arup Guha
// 5/12/2015
// Solution to FHSPS Problem: Theme Park Speed

// Uses Floyd Warshall's Algorithm - the bounds of the problem were created to allow
// this solution, which is slower and uses more memory than running Dijkstra's.

// The trick here is to represent each location in the original graph with 2 vertices
// in the input graph, so we can determine if the last path taken was run or walked.

import java.util.*;

public class speed2 {

	public static void main(String[] args) {

		Scanner stdin = new Scanner(System.in);
		int numCases = stdin.nextInt();

		// Process each case.
		for (int loop=0; loop<numCases; loop++) {

			int v = stdin.nextInt();
			int e = stdin.nextInt();
			int source = stdin.nextInt();
			int dest = stdin.nextInt();
			int n = 2*v+2;

			// We double each vertex and add a new source and destination for ease.
			int[][] graph = new int[n][n];
			for (int i=0; i<n; i++) {
				Arrays.fill(graph[i], 1000000000);
				graph[i][i] = 0;
			}

			// Add edges.
			for (int i=0; i<e; i++) {

				// Get the two edges.
				int v1 = stdin.nextInt();
				int v2 = stdin.nextInt();
				int slow = stdin.nextInt();
				int fast = stdin.nextInt();

				// Since they are undirected, we add both directions.
				// Also, note that we are ALWAYS allowed to take the slow edge.
				graph[2*v1][2*v2+1] = fast;
				graph[2*v1][2*v2] = slow;
				graph[2*v1+1][2*v2] = slow;

				graph[2*v2][2*v1+1] = fast;
				graph[2*v2][2*v1] = slow;
				graph[2*v2+1][2*v1] = slow;
			}

			// source to both "slow" and "fast" start vertex - one way.
			graph[2*v][2*source] = 0;
			graph[2*v][2*source+1] = 0;

			// both destinations to the added end vertex - one way.
			graph[2*dest][2*v+1] = 0;
			graph[2*dest+1][2*v+1] = 0;

			// Run Floyd's.
			for (int k=0; k<n; k++)
				for (int i=0; i<n; i++)
					for (int j=0; j<n; j++)
						graph[i][j] = Math.min(graph[i][j], graph[i][k]+graph[k][j]);

			// All we have to print.
			System.out.println(graph[2*v][2*v+1]);
		}
	}
}