408210: GYM103055 D Shortest Path Query

There is an undirected graph with $$$n$$$ vertices and $$$m$$$ edges. The vertices are labelled by $$$1,2,\dots,n$$$. The $$$i$$$-th edge connects the $$$u_i$$$-th vertex and the $$$v_i$$$-th vertex, the length of which is $$$w_i$$$. Here, $$$u_i$$$'s binary representation is always a prefix of $$$v_i$$$'s binary representation. Both binary representations are considered without leading zeros. For example, $$$u_i=2_{10}=\textbf{10}_2$$$, $$$v_i=5_{10}=\textbf{10}1_{2}$$$.

You will be given $$$q$$$ queries. In the $$$i$$$-th query, you will be given two integers $$$s_i$$$ and $$$t_i$$$. Please write a program to figure out the length of the shortest path from the $$$s_i$$$-th vertex to the $$$t_i$$$-th vertex, or determine there is no path between them.

The input contains only a single case.

The first line of the input contains two integers $$$n$$$ and $$$m$$$ ($$$1 \leq n \leq 100\,000$$$, $$$1\leq m\leq 200\,000$$$), denoting the number of vertices and the number of edges.

In the next $$$m$$$ lines, the $$$i$$$-th line $$$(1 \le i \le m)$$$ contains three integers $$$u_i,v_i$$$ and $$$w_i$$$ ($$$1\le u_i<v_i\leq n$$$, $$$1\leq w_i\leq 10^9$$$), describing the $$$i$$$-th edge. It is guaranteed that $$$u_i$$$'s binary representation is a prefix of $$$v_i$$$'s binary representation.

In the next line, there contains a single integer $$$q$$$ ($$$1\leq q\leq 200\,000$$$), denoting the number of queries.

In the next $$$q$$$ lines, the $$$i$$$-th line $$$(1 \le i \le q)$$$ contains two integers $$$s_i$$$ and $$$t_i$$$ ($$$1\leq s_i,t_i\leq n$$$, $$$s_i\neq t_i$$$), describing the $$$i$$$-th query.

For each query, print a single line containing an integer, denoting the length of the shortest path. If there is no path, print "-1" instead.

5 6
1 2 4
1 3 2
1 4 5
1 5 8
2 4 3
2 5 2
4
2 3
1 4
1 5
4 5

6
5
6
5

3 1
1 2 100
3
1 2
1 3
2 3

100
-1
-1