408397: GYM103114 A Aahaxiki's journey I - set off

Maybe one day, Fahaxiki will go to a city far away to participate in the competition. The inexperienced Fahaxiki hopes that you can help them plan their routes so that they can spend the least RMB and hours to reach their destination.

There are $$$n$$$ cities in the country, connected by $$$m$$$ railways and $$$l$$$ air routes, all of which are regarded as undirected roads. Obviously, schools, train stations, airports and competition sites in a city should be in four different locations. It is known that it takes $$$x$$$ RMB and $$$y$$$ hours to move between any two locations in the same city.

Suppose Fahaxiki is in a school located in city $$$1$$$, and needs to go to the competition site in city $$$n$$$ to participate in the competition. Please find the minimum cost and hours to reach the destination. Prioritize the least cost. If there are multiple paths with the least cost, choose the least hours-consuming solution.

The first line contains one integer $$$T(1 \leq T \leq 10^5)$$$, which represents the number of test case.

For each test case, the first line consists of five integers $$$n, m, l, x, y (1 \leq n \leq 10^5, 0 \leq m, l \leq 10^5, 1 \leq x, y \leq 10^3)$$$, $$$n$$$ cities, $$$m$$$ railways, $$$l$$$ air routes. And it takes $$$x$$$ RMB and $$$y$$$ hours to move between any two locations in the same city.

Each of the next $$$m$$$ lines contains four integers $$$u_i, v_i, a_i, b_i (1 \leq u_i, v_i, \leq n, 1 \leq a_i, b_i \leq 10^3)$$$, indicates that there is a railway connecting city $$$u_i$$$ and city $$$v_i$$$, which costs $$$a_i$$$ RMB and $$$b_i$$$ hours.

Each of the next $$$l$$$ lines contains four integers $$$u_i, v_i, a_i, b_i (1 \leq u_i, v_i, \leq n, 1 \leq a_i, b_i \leq 10^3)$$$, indicates that there is a air route connecting city $$$u_i$$$ and city $$$v_i$$$, which costs $$$a_i$$$ RMB and $$$b_i$$$ hours.

The sum of $$$n$$$ over all test cases doesn't exceed $$$10^6$$$.

The sum of $$$(m + l)$$$ over all test cases doesn't exceed $$$10^6$$$.

For every prediction if there is a route to the destination, output the minimum cost and hours, otherwise output -1.

2
3 2 1 50 1
1 2 300 25
2 3 140 10
1 3 450 3
4 3 2 100 2
1 2 600 20
1 4 1000 40
3 4 700 21
2 4 300 2
1 3 200 2

540 37
1200 28

In the first example, the action route is: city 1 school -> city 1 train station -> city 2 train station -> city 3 train station -> city 3 competition site, it costs 540RMB and 37 hours.

In the second example, the action route is: City 1 School -> City 1 train station -> City 2 train station -> City 2 Airport -> City 3 Airport -> City 3 Competition Site, it costs 1200RMB and 28 hours in total