题目描述

FJ 有 $N$ 头奶牛 $(2\le N\le 1000)$，编号为 $1\ldots N$。奶牛们将按照编号顺序排成一列队伍（可能有多头奶牛在同一位置上）。换句话说，假设 i 号奶牛位于$P_{\!\;i}$，则 $P_{\,1}\le P_{\,2}\le \ldots\le P_{\!\;N}$。

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

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

请计算：如果满足上述所有条件，1 号奶牛和 N 号奶牛之间的距离$（P_{\!\;N}-P_{\,1}）$最大为多少。

输入格式

第一行：三个整数$N, M_L, M_D$，用空格分隔。 第 $2\dots M_L+1$ 行：每行三个整数 $A, B, D$，用空格分隔，表示 $P_B-P_A\le D$。 第$M_L+2\dots M_L+M_D+1$ 行：每行三个整数 A, B, D，用空格分隔，表示 $P_B-P_A\ge D$。 保证 $1\le A<B\le N, 1\le D\le 10^6$。

输出格式

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

样例

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

27

这四头牛分别位于 $0,7,10,27$。

数据范围与提示

对于全部数据，$2\le N\le 1000$,$1\le M_L,M_D\le 10^4,1\le L,D\le 10^6$。