A skiing competition is taking place. There are 
~N~ points on the hill and 
~M~ trails to get from one to another. It takes 
~t_m~ seconds to get from point 
~a_m~ to 
~b_m~ (and back) on the 
~m^\text{th}~ trail. It takes the same amount of time to get back on the same trail. The competition starts from 
~A~ and goes to 
~B~. There are 
~Q~ competitors racing. Due to rigging of the race, the 
~q^\text{th}~ competitor will take the 
~{k_q}^\text{th}~ fastest path. Two paths are identical in rank if they take the same amount of time. A competitor may not go back to a previously visited point.
To prepare the competitors, you will provide each of them with two pieces of information, the time they will take to finish the race, and the minimum time they will spend on one trail.
Constraints
For all subtasks:
~1 \le A, B \le N~, 
~A \ne B~
~0 \le t_m \le 10^6~
Subtask 1 [20%]
~2 \le N \le 100~
~Q = k_0 = 1~
~0 \le M \le \frac{N(N-1)}{2}~
Subtask 2 [20%]
~2 \le N \le 100~
~1 \le Q, k_q \le 10~
~0 \le M \le \frac{N(N-1)}{2}~
Subtask 3 [20%]
~2 \le N \le 1000~
~Q = k_0 = 1~
~0 \le M \le N \log N~
Subtask 4 [40%]
~2 \le N \le 1000~
~1 \le Q, k_q \le 50~
~0 \le M \le N \log N~
Input Specification
The first line will contain, ~N~ ~M~ ~A~ ~B~ ~Q~, all space separated.
The next ~M~ lines will contain three integers, ~a_m~ ~b_m~ and ~t_m~ meaning a trail from ~a_m~ to ~b_m~ (and vice versa) will take ~t_m~ units of time to ski.
The next ~Q~ lines will contain a single integer, 
~k_q~, the designated path that the ~q^\text{th}~ competitor will take.
Output Specification
~Q~ lines containing two integers, the time it will take this competitor to finish the race, and the fastest time this competitor can take to get from one point to another. If there are no more paths, output -1 for that query.
Sample Input
5 8 1 5 4
1 2 1
1 3 2
2 3 3
3 4 2
3 5 3
2 4 1
4 5 1
1 5 5
1
2
3
4
Sample Output
3 1
5 1
7 1
-1
Explanation for Sample Output
The trails look like the following:
The fastest path is 
~1 \to 2 \to 4 \to 5~.
The second fastest path is 
~1 \to 3 \to 4 \to 5~.
The third fastest (slowest) path is 
~1 \to 3 \to 2 \to 4 \to 5~.
A fourth path doesn't exist.
The fastest trail on all these paths is 
~1~ unit of time.
Comments
it says paths are identical in rank if they are equal. however, do they count as multiple paths still? example: If there were paths of length 4, 6, 6 and 8, would the ranks be 1, 2, 2 and 3 or 1, 2, 2 and 4. Also, if the minimum-path is different for two paths of the same length, what do we output?
It's 1, 2, 2, 3. Take the path that minimizes the minimum trail.