该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

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

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

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

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

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

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

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

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

输入格式

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

对于每组测试数据：

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

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

接下来 $N2$ 行每行包含三个整数 $x, y, z$，分别表示 llh 认为 $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

样例解释

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

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