说明

ykw 家里有很多很多很多的摆件，有各种动漫人气角色的手办，有各种游戏周边，有各种盲盒娃娃，甚至还有高达系列模型

这么多的摆件如果随意摆放在柜子上，就显得很丑。

同一个系列的摆件当然要放在一起才好看，而有些不同系列的摆件放在一起，则显得格格不入。

现在 ykw 想要把自己家里的这么多摆件重新摆一下位置，让它们变得好看一些。

ykw 将所有摆件从 1 ~ n 编号，并且按照编号大小从小到大排列成一排放好（所有摆件的相对顺序不能改变）

但是他只能想到，比如某两个摆件靠的近比较好看，那它们之间的距离不应该超过多少，比如某两个摆件离得近就显得难看，那它们之间的距离至少是多少。

现在 ykw 想知道 1 号摆件和 n 号摆件摆放时的最远距离是多少，以便于他可以去定制对应的柜子。

当然，任意两个摆件之间的距离必须是正整数。

输入格式

输入第一行包含一个正整数 T，表示有 T 组测试数据

对于每组测试数据：

第一行输入三个整数 n, N1, N2 分别表示摆件数量 n, ykw 觉得好看的摆件关系有 N1 对，不好看的摆件关系有 N2 对

接下来 N1 行每行包含三个整数 x, y, z，分别表示 ykw 认为 x 号摆件和 y 号摆件放在一起是好看的，它们之间的距离最远是 z

接下来 N2 行每行包含三个整数 x, y, z，分别表示 ykw 认为 x 号摆件和 y 号摆件放在一起是难看的，它们之间的距离至少是 z

对于 40\% 的数据，T <= 5,n <= 100, 0 <= N1,N2 <= 500 ,1 <= z <= 500

对于 100\% 的数据，T <= 5,n <= 1000; 0 <= N1,N2 <= 10000; 1 <= z <= 1000000

对于所有的数据保证 1 <= x < y <= n

输出格式

如果不存在合法的摆件方式，则输出 -1

如果 1 号摆件和 n 号摆件之间的距离没有上限，则输出 -2

否则输出 1 号摆件和 n 号摆件之间的最大距离

样例

1
4 2 1
2 4 22
1 3 11
2 3 5

28

提示

2 和 4 的距离不能超过 22
1 和 3 的距离不能超过 11
2 和 3 的距离最少是 5

所以最终的摆放方式为
1-2 间隔 6 
2-3 间隔 5
3-4 间隔 17
得到最远距离为 28