Description

有一张\(n\)个点\(m\)条边的无向图，第\(i\)条边连接\(u_i\)和\(v_i\)号顶点，边权为\(w_i\)。
非常奇怪的事情是，\(u_i\)的二进制表示一定是\(v_i\)的二进制表示的前缀（均无前导零）。
你需要处理\(q\)组询问，每次询问\(s\)到\(t\)的最短路长度。

Format

Input

每个测试点仅包含一组测试数据。
第一行两个整数\(n,m(1<=n<=100000,1<=m<=200000)\)。
接下来\(m\)行，每行三个整数\(u,v,w(1<=u<v<=n,1<=w<=10^9)\)，表示一条边。
接下来一行一个整数\(q(1<=q<=200000)\)。
接下来\(q\)行，每行两个互异整数\(s,t(1<=s,t<=n)\)。

Output

按照输入顺序，对于每组询问输出最短路长度，如不可达输出\(-1\)。

Sample 1

Input

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

Output

6
5
6
5

Limitation

2s, 1GB for each test case.

Subtasks

子任务1（30分）：\(n,m,q<=2000\)。
子任务2（30分）：任意两点之间至多只有一条简单路径。
子任务3（40分）：无附加限制。

Source

Vijos Original