Fry is an intergalactic delivery boy that spends all day trying to impress Lila. He wants to prove her that he's a smart guy so he wants to find routs between the different planets he must travel to by himself. Of course, he wants these routs to be as short as possible. Because of space pirates, meteor showers and other dangerous things, it's safe to travel only between certain pairs of planets. Help him find a good delivery plan so he can win Lila's heart. By Fry's observations, there is a safe route between any 2 destinations and the shortest one always passes through no more then 50 planets.

Input

The first line of input contains 2 integer, N and M (N≤50.000, M≤250.000), representing the number of planets and the number of direct routs between them. The next M lines contain 3 integers, X, Y, L (1≤L≤1.000.000) meaning that there is a safe connexion between planet X and planet Y of length L. The M+2-th line contains a number NQ (NQ≤5.000) and then follow NQ lines with 2 integers A and B meaning that Fry should take a package from planet A to B.

Output

Output must contain NQ lines, each line containing a number Nr (Nr≤100) and Nr integers representing the planets in the order you visit them. If Nr is -1 then that means that you want to skip this query.

Score

For each answered query you will receive (Best/Length)² points, where Best is the shortest length you can get when traveling between the planets you should have delivered a package and Length is the length of your route.

Example

Input:
5 5
1 4 1
2 1 2
2 5 2
4 5 2
2 3 3
3
1 5
3 4
3 1

Output:
3 1 4 5
4 3 2 1 4
3 3 2 1

Notes: This solution should receive 3 points. If you don't get AC on one of the 6 input cases, your score on that test case is 0 but you keep the points from the other inputs.