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

// Uses an efficient implementation of Dijkstra's Algorithm.
// 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 speed {

	public static int v;
	public static int e;
	public static ArrayList[] graph;
	public static int source;
	public static int dest;

	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++) {

			v = stdin.nextInt();
			e = stdin.nextInt();
			source = stdin.nextInt();
			dest = stdin.nextInt();

			// We double each vertex and add a new source and destination for ease.
			graph = new ArrayList[2*v+2];
			for (int i=0; i<graph.length; i++)
				graph[i] = new ArrayList<edge>();

			// 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, but we have to
				// be careful because fast edges must always go into odd vertices.
				// Also, note that we are ALWAYS allowed to take the slow edge.
				// This is a directed graph, for these reasons.
				graph[2*v1].add(new edge(2*v2+1, fast));
				graph[2*v1].add(new edge(2*v2, slow));
				graph[2*v1+1].add(new edge(2*v2, slow));

				graph[2*v2].add(new edge(2*v1+1, fast));
				graph[2*v2].add(new edge(2*v1, slow));
				graph[2*v2+1].add(new edge(2*v1, slow));
			}

			// source to both "slow" and "fast" start vertex - one way.
			graph[2*v].add(new edge(2*source, 0));
			graph[2*v].add(new edge(2*source+1, 0));

			// both destinations to the added end vertex - one way.
			graph[2*dest].add(new edge(2*v+1, 0));
			graph[2*dest+1].add(new edge(2*v+1, 0));


			// Probably bad style, but we'll run Dijkstra's here.
			edge[] best = new edge[2*v+2];
			Arrays.fill(best, null);

			PriorityQueue<edge> pq = new PriorityQueue<edge>();
			for (int i=0; i<graph[2*v].size(); i++) {
				pq.offer((edge)graph[2*v].get(i));
				best[((edge)graph[2*v].get(i)).ID] = (edge)graph[2*v].get(i);
			}

			int res = 1000000000;

			// Go till priority queue is empty.
			while (pq.size() > 0) {

				// Get next.
				edge next = pq.poll();
				int curV = next.ID;
				int curW = next.weight;

				// Found it!
				if (curV == 2*v+1) {
					res = curW;
					break;
				}

				// Enqueue neighbors for which we don't have shortest distances.
				for (int i=0; i<graph[curV].size(); i++) {
					edge nextEdge = (edge)graph[curV].get(i);
					edge newEdge = new edge(nextEdge.ID, curW+nextEdge.weight);
					if (best[nextEdge.ID] == null) {
						pq.offer(newEdge);
						best[nextEdge.ID] = newEdge;
					}
					else if (curW+nextEdge.weight < best[nextEdge.ID].weight) {
						pq.remove(best[nextEdge.ID]);
						pq.offer(newEdge);
						best[nextEdge.ID] = newEdge;
					}
				}
			}

			// All we have to print.
			System.out.println(res);
		}
	}
}

class edge implements Comparable<edge> {

	public int ID;
	public int weight;

	public edge(int number, int w) {
		ID = number;
		weight = w;
	}

	public int compareTo(edge other) {
		return this.weight - other.weight;
	}
}