题目描述

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

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

输入格式

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

接下来有n个模块，每块描述一个国家的情况。每个模块的第一行是一个正整数mi，表示编号为i的国家包含的城市个数，接下来mi-1行，每行包含三个整数u，v，t，表示从城市u到城市v有通路，需要花费的时间为t (1<=t<=1000)。

接下来一行有一个正整数q，表示查询的个数。接下来q行，每一行包含四个整数，s0，s1，e0，e1，其中，(s0,s1)为出发地，(e0,e1)为目的地。

输出格式

输出有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<=10，∑mi<=1000，q<=10。

对于60%的数据，n<=1000，∑mi<=1000000。

对于100%的数据，n<=350000，∑mi<=1000000，1<=t<=1000，q<=100000。