The Shopping Plan of Groundhog
题号：NC208948
时间限制：C/C++/Rust/Pascal 6秒，其他语言12秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

Apple’s birthday is coming, so Groundhog wants to buy gifts for Apple. The city where Groundhog is located has a bustling shopping belt consisting of  traffic stops and  undirected shopping streets, and it is guaranteed that any two traffic stops can reach each other only through these shopping streets. The  shopping street connects the sites u_i and v_i. On each shopping street, Groundhog can cross it from the left or right side of the street, which costs l_i and r_i respectively.(Whether he crosses from u_i to v_i or from v_ito u_i, he can choose to cross from the left or the right side of the street)

Of course, Groundhog did not forget to buy gifts for Apple. On each shopping street, if he pass by on the left, he can spend x_i to buy a gift, and when he pass by on the right, he can spend y_i to buy another.

Apple wanted  birthday gifts, so she made  gift requests. For the  gift request, Groundhog can start from the site s_i and walk along the shopping street to t_i (each shopping street on this path must be passed through). For each shopping street, he can choose to cross from the left or right (the choice of different shopping streets is independent), and choose exactly one gift along the way to give to Apple (note that if Groundhog crosses a shopping street from the left, then the gift on the right will not be counted and vice versa). In order to reflect his concern for Apple, Groundhog will always choose the most expensive gift along the way; but Groundhog is not wealthy, so he will choose a scheme to minimize the total cost of his travel expenses and money used to buy gifts.

Groundhog is lazy so he throws this question to you. You need to know how much Groundhog will cost for each gift request from Apple (including the cost of buying gifts and road expenses).

输入描述:

The first line contains two integers  and , which represent the number of traffic stops and the number of gift requests made by Apple.
The next  lines, each line includes six integers u_i, v_i, l_i, r_i, x_i, y_i, meaning as shown above.
The next  lines, each line includes two integers s_i,t_i, meaning as shown above.

输出描述:

Output  lines indicating how much groundhog will cost at least for each Apple gift request(specially, if ,just output 0 for this request).
示例1

输入

复制 
5 5
1 2 1 2 1 2
1 3 2 1 1 2
3 4 3 2 1 5
3 5 2 3 3 1
1 5
2 3
2 5
4 5
1 1

输出

复制 
6
4
7
7
0

备注:

.