题目描述

有 $n$ 个国家，编号分别为 $0$ 到 $n-1$。第 $i$ 个国家包含 $m_i$ 个城市，编号分别为 $0$ 到 $m_{i}-1$，其中编号为 $0$ 的城市是该国家的首都。为了表示的方便，我们用 $(i,j)$ 来表示第 $i$ 个国家的第 $j$ 个城市。同一个国家的城市之间有通路，这些通路构成一棵树，首都则是这棵树的根。而不同国家的城市之间没有通路，只能通过传送门。每个国家只有处于叶子节点的城市具有传送门，传送门的目的地可以是编号相邻的国家的任意一个处于叶子节点的城市，每次传送需要花费 $1$ 个单位时间，并且每个传送门只能使用一次。如下图所示，如果出发地是 $(0,2)$，目的地是 $(2,1)$，则 $(0,2)\rightarrow(1,1)\rightarrow(1,0)\rightarrow(1,2)\rightarrow(2,1)$ 是一条可行路径，而 $(0,2)\rightarrow(1,1)\rightarrow(2,1)$ 则是非法的，因为 $(1,1)$ 的传送门在 $(0,2)\rightarrow(1,1)$ 的时候被使用了一次，在 $(1,1)\rightarrow(2,1)$ 的时候又被使用了一次。

给定出发地和目的地，问最少需要多少时间。

输入格式

输入第一行有一个正整数 $n$。

接下来有 $n$ 个模块，每块描述一个国家的情况。每个模块的第一行是一个正整数 $m_i$，表示编号为 $i$ 的国家包含的城市个数，接下来 $m_{i}-1$ 行，每行包含三个整数 $u,v,t$，表示从城市 $u$ 到城市 $v$ 有通路，需要花费的时间为 $t (1 \leq t \leq 10^{3})$。

接下来一行有一个正整数 $q$，表示查询的个数。接下来 $q$ 行，每一行包含四个整数，$s_0,s_1,e_0,e_1$，其中，$(s_0,s_1)$ 为出发地，$(e_0,e_1)$ 为目的地。

输出格式

输出有 $q$ 行，每行只包含一个整数。如果能从出发地到达目的地，输出最少时间，否则，输出 $-1$。

5
3
0 1 1
0 2 1
3
0 1 2
2 0 1
3
0 1 1
0 2 1
2
0 1 2
3
0 1 1
0 2 1
3
0 2 2 1
0 0 2 1
2 2 4 1

5
6
-1

提示

对于 $40\%$ 的数据，$n \leq 10,\sum m_i \leq 10^{3},q \leq 10$。

对于 $60\%$ 的数据，$n \leq 10^{3},\sum m_i \leq 10^{6}$。

对于 $100\%$ 的数据，$n \leq 3.5 \times 10^{5},\sum m_i \leq 10^{6},1 \leq t \leq 10^{3},q \leq 10^{5}$。