Problem statement:

 

A graph of a country is given. There are N cities and M number of roads. Each road connect two cities. Now you are given two modes of traveling from one city to another.

 

-> By using public transportation.

 

-> By using your own car.(which you can use only once between any two cities on your way). You may or maynot use this mode of travel.

 

The country's map is given as a graph with N nodes (labeled from 1 to N), and the initial station is node S and the destination is node D. There are two undirected edges between each of the given nodes:

 

-> one denotes the cost of a path using public transportation, r.

 

-> and the other denotes the cost of a path using your own car, t.

 

Now you have to find the most optimal way (in terms of time of cost) from S to D with or without using your entitled car ride. Output the minimized cost of your travel from the source to the destination.

 

Input:

 

The first line contains T, the number of test cases.

 

For each test case:

 

The first line contains two space-separated integers, N (the number of cities in the map) and M (the number of roads in the map), respectively.

 

The next M lines each have four space separated integers c1, c2, r, and t, respectively; c1 and c2 denote two cities connected by a road, r is the cost for using the public transportation, and t is the cost of taking your own car on the road.

 

The last line has two space-separated integers, S (Starting city) and D (Destination), respectively.

 

Constraints:

 

1 ≤ T ≤ 10

2 ≤ N ≤ 3000

1 ≤ M≤ N×(N−1)

1 ≤ x, y, S,D ≤ N

1 ≤ r, t ≤ 500

 

Output:

For each test case, print a single line with minimum travel cost. If the destination (D) is unreachable from the source node (S), print −1.

 

Sample input:

1

4 5

1 2 6 5

1 3 4 5

2 3 6 1

2 4 3 4

3 4 5 7

1 4

 

Sample output:

8