题目背景

正如其他物种一样，奶牛们也喜欢在排队打饭时与它们的朋友挨在一起。

题目描述

FJ 有编号为 $1\dots N$ 的 $N$ 头奶牛（$2\le N\le 1000$）。奶牛们始终需要按照编号顺序来排队。奶牛们很笨拙，因此可能有多头奶牛在同一位置上。

有些奶牛是好基友，它们希望彼此之间的距离小于等于某个数。有些奶牛是情敌，它们希望彼此之间的距离大于等于某个数。

给出 $M_L$ 对好基友的编号，以及它们希望彼此之间的距离小于等于多少；又给出 $M_D$ 对情敌的编号，以及它们希望彼此之间的距离大于等于多少（$1\le M_L, M_D\le 10^4$）。

请计算：如果满足上述所有条件，$1$ 号奶牛和 $N$ 号奶牛之间的距离最大为多少。

输入格式

第一行：三个整数 $N, M_L, M_D$，用空格分隔。

第 $2\dots M_L+1$ 行：每行三个整数 $A, B, D$，表示 $A$ 号奶牛与 $B$ 号奶牛之间的距离须 $\le D$。保证 $1\le A < B\le N$，$1\le D\le 10^6$。

第 $M_L+2\dots M_L+M_D+1$ 行：每行三个整数 $A, B, D$，表示 $A$ 号奶牛与 $B$ 号奶牛之间的距离须 $\ge D$。保证 $1\le A < B\le N$，$1\le D\le 10^6$。

输出格式

一行，一个整数。如果没有合法方案，输出 -1。如果有合法方案，但 $1$ 号奶牛可以与 $N$ 号奶牛相距无穷远，输出 -2。否则，输出 $1$ 号奶牛与 $N$ 号奶牛间的最大距离。

输入示例 1

4 2 1
1 3 10
2 4 20
2 3 3

输出示例 1

27

示例 1 说明

4头奶牛，奶牛1和3距离不超过10，奶牛2和4距离不超过20，奶牛2和3距离不小于3。

最优方案：奶牛1在坐标0，奶牛2在7，奶牛3在10，奶牛4在27，此时距离为27。

约束条件

• $2\le N\le 1000$
• $1\le M_L, M_D\le 10^4$
• $1\le D\le 10^6$