{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"就像其他动物一样,奶牛在排队等待饲料时也喜欢靠近朋友。FJ有N头(2 \u003c\u003d N \u003c\u003d 1,000)编号为1..N的奶牛沿着一条直线站成一排等待饲料。奶牛的站立顺序和它们的编号相同,由于它们可能会有些强势,所以有可能两头或更多的奶牛站在完全相同的位置(也就是说,如果我们把每头奶牛看作在数轴上的某个坐标,那么有可能两头或更多的奶牛共享相同的坐标)。\n\n有些奶牛彼此喜欢,并希望在队列中保持一定的距离。有些奶牛彼此不喜欢,并希望至少保持一定的距离。一系列ML(1 \u003c\u003d ML \u003c\u003d 10,000)约束描述了哪些奶牛彼此喜欢以及它们之间可以保持的最大距离;随后的一系列MD约束(1 \u003c\u003d MD \u003c\u003d 10,000)描述了哪些奶牛彼此不喜欢以及它们之间必须保持的最小距离。\n\n你的任务是计算并输出满足距离约束条件下,奶牛1和奶牛N之间可能的最大距离。"}},{"title":"输入","value":{"format":"HTML","content":"第1行:三个以空格分隔的整数:N、ML和MD。\n\n第2行到ML+1行:每行包含三个以空格分隔的正整数:A、B和D,其中1 \u003c\u003d A \u003c B \u003c\u003d N。奶牛A和B之间的距离最多为D(1 \u003c\u003d D \u003c\u003d 1,000,000)。\n\n第ML+2行到ML+MD+1行:每行包含三个以空格分隔的正整数:A、B和D,其中1 \u003c\u003d A \u003c B \u003c\u003d N。奶牛A和B之间的距离至少为D(1 \u003c\u003d D \u003c\u003d 1,000,000)。"}},{"title":"输出","value":{"format":"HTML","content":"第1行:一个整数。如果无法排队,输出-1。如果奶牛1和N可以任意远离,输出-2。否则输出奶牛1和N之间可能的最大距离。"}},{"title":"样例","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e4 2 1\r\n1 3 10\r\n2 4 20\r\n2 3 3\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e27\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}},{"title":"提示","value":{"format":"HTML","content":"样例解释:\n\n有4头奶牛。奶牛1和奶牛3之间的距离最多为10个单位,奶牛2和奶牛4之间的距离最多为20个单位,奶牛2和奶牛3不喜欢彼此,它们之间的距离至少为3个单位。\n\n在数轴上,最佳的排列方式是:奶牛1在0处,奶牛2在7处,奶牛3在10处,奶牛4在27处。"}}]}