Chase The Light
Description
In Minerva, there are $N$ floating islands connected by $M$ bidirectional rainbow bridges. Each bridge has a different brightness and the length of each bridge is $1$. Throughout the lands, There are $Q$ animals that are trying to see the festival of light and darkness on island $1$. These animals can either be white or black. The animals all want to get to their destination while travelling the shortest distance. If there are many paths of the same distance, the white animals will try to maximize the total brightness of the bridges they cross, while the black animals will try to minimize it. Calculate the distance each animal will travel and the total brightness they will encounter on their journey.
Note: it will always be possible for each animal to reach island 1.
The first line contains $N$ and $M$.
The next $M$ lines are in the form $x$ $y$ $z$ representing a path between $x$ and $y$ with a brightness $z$.
The next line contains $Q$.
The next $Q$ lines contain $d_i$, the initial location of the $i$th animal, followed by either 'White' or 'Black', representing their color.
##Constraints
$1 \le x,y,d_i \le N \le 5 \times 10^5$
$1 \le z \le 256$
$N-1 \le M \le 10^6$
$1 \le Q \le 10^5$
For each of the $Q$ animals, output the length and brightness of their best path.
Input
The first line contains $N$ and $M$.
The next $M$ lines are in the form $x$ $y$ $z$ representing a path between $x$ and $y$ with a brightness $z$.
The next line contains $Q$.
The next $Q$ lines contain $d_i$, the initial location of the $i$th animal, followed by either 'White' or 'Black', representing their color.
##Constraints
$1 \le x,y,d_i \le N \le 5 \times 10^5$
$1 \le z \le 256$
$N-1 \le M \le 10^6$
$1 \le Q \le 10^5$
Output
For each of the $Q$ animals, output the length and brightness of their best path.
5 7
4 1 7
5 2 1
5 3 9
5 4 5
1 5 1
3 1 8
3 4 6
5
2 Black
5 Black
3 Black
3 White
1 White
2 2
1 1
1 8
1 8
0 0