[{"sectionTitle":"题目描述","type":"Text","text":"原题来自：USACO 2005 Dec. Gold\r\n\r\nFJ 有 $N$ 头奶牛 $(2\\le N\\le 1000)$，编号为 $1\\ldots N$。奶牛们将按照编号顺序排成一列队伍（可能有多头奶牛在同一位置上）。换句话说，假设 $i$ 号奶牛位于 $P_{\\!\\;i}$，则 $P_{\\,1}\\le P_{\\,2}\\le \\ldots\\le P_{\\!\\;N}$。\r\n\r\n有些奶牛是好基友，它们希望彼此之间的距离小于等于某个数。有些奶牛是情敌，它们希望彼此之间的距离大于等于某个数。\r\n\r\n给出 $M_L$ 对好基友的编号，以及它们希望彼此之间的距离小于等于多少；又给出 $M_D$ 对情敌的编号，以及它们希望彼此之间的距离大于等于多少 $(1\\le M_L,$ $M_D\\le 10^4)$。\r\n\r\n请计算：如果满足上述所有条件，$1$ 号奶牛和 $N$ 号奶牛之间的距离（$P_{\\!\\;N}-P_{\\,1}$）最大为多少。","subType":"markdown"},{"sectionTitle":"输入格式","type":"Text","text":"第一行：三个整数 $N, M_L, M_D$，用空格分隔。 \r\n第 $2\\dots M_L+1$ 行：每行三个整数 $A, B, D$，用空格分隔，表示 $P_B-P_A\\le D$。 \r\n第 $M_L+2\\dots M_L+M_D+1$ 行：每行三个整数 $A, B, D$，用空格分隔，表示 $P_B-P_A\\ge D$。 \r\n保证 $1\\le A<B\\le N,$ $1\\le D\\le 10^6$。","subType":"markdown"},{"sectionTitle":"输出格式","type":"Text","text":"一行，一个整数。如果没有合法方案，输出 $\\texttt{-1}$. 如果有合法方案，但 $1$ 号奶牛可以与 $N$ 号奶牛相距无穷远，输出 $\\texttt{-2}$. 否则，输出 $1$ 号奶牛与 $N$ 号奶牛间的最大距离。","subType":"markdown"},{"sectionTitle":"样例","type":"Sample","text":"这四头牛分别位于 $0,7,10,27$。","subType":"markdown","payload":["4 2 1\n1 3 10\n2 4 20\n2 3 3","27"]},{"sectionTitle":"数据范围与提示","type":"Text","text":"对于全部数据，$2\\le N\\le 1000,1\\le M_L,M_D\\le 10^4,1\\le L,D\\le 10^6$。","subType":"markdown"}]