暂无测试数据。

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

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

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

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

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

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

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

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

输入格式

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

对于每组测试数据：

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

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

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

输出格式

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

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

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

数据范围

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

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

对于所有的数据保证 $1 \leq x < y \leq n$。

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

28