【题目描述】

C国的道路网络由若干条双向线路组成。每条线路途经一些城市(可能会经过多次同一城市)，位于线路上的两个城市a，b通过i号线路互相抵达的费用为 w[i][a] + w[i][b]。现在有若干个询问，询问两城市互相到达的最小费用。

【输入数据】

第一行为城市数n与线路数m。

以下m行每行描述一条线路：

第一个正整数l[i]为i号线路途经的城市数，接下来2*l[i]个正整数，每两个数描述一个城市，依次表示途经的城市j，费用w[i][j]；接下来若干行每行两个正整数a，b表示询问a，b之间的最小费用，最后以0 0结束。

【输出数据】

对于每组询问输出一行。

若不存在路径输出 -1，否则输出最小费用。

【样例输入】

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

【样例输出】

2
7
3

【数据范围】

令T为询问数

10%的数据满足n≤10,m≤3,T≤3。

30%的数据满足n,T≤100,m,l[i]≤15。

50%的数据满足n≤1000,T≤100,m,l[i]≤50。

100%的数据满足n≤100000,m≤300,T,l[i],w[i][j]≤2000。