{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"FJ的奶牛非常讨厌被淋湿,以至于一想到被雨淋到就会在蹄子上发抖。它们决定在农场上安装雨警报器,以便在雨要来临时通知它们。它们打算制定一个雨避难计划,让所有奶牛在雨开始前都能找到避难所。不过,天气预报并不总是准确。为了尽量减少虚警,它们希望在尽可能晚的时候响起警报,同时又能给所有奶牛足够的时间找到避难所。\n\n\u003cbr\u003e\n\u003cbr\u003e\n农场上有F(1 \u003c\u003d F \u003c\u003d 200)块牧场,奶牛在这些牧场上吃草。有一组P(1 \u003c\u003d P \u003c\u003d 1500)条路径连接着这些牧场。这些路径很宽,所以任意数量的奶牛都可以沿着路径双向行走。\n\n\u003cbr\u003e\n\u003cbr\u003e\n农场上的一些牧场下面有雨避难所,奶牛可以在这些避难所下躲雨。这些避难所有一定的容量,所以一个避难所可能无法容纳所有的奶牛。牧场相对于路径来说很小,奶牛在牧场之间行走不需要时间。\n\n\u003cbr\u003e\n\u003cbr\u003e\n计算在雨开始前,必须要在多少时间内响起警报,以便每头奶牛都能找到避难所。"}},{"title":"输入","value":{"format":"HTML","content":"* 第1行: 两个用空格分隔的整数:F 和 P\n\n\u003cbr\u003e\n\u003cbr\u003e\n* 第2行到第F+1行: 每行有两个用空格分隔的整数,描述一个牧场。第一个整数(范围:0..1000)表示该牧场中的奶牛数量。第二个整数(范围:0..1000)表示该牧场的避难所可以容纳的奶牛数量。第i+1行描述第i个牧场。\n\n\u003cbr\u003e\n\u003cbr\u003e\n* 第F+2行到第F+P+1行: 每行有三个用空格分隔的整数,描述一条路径。前两个整数(范围都为1..F)表示路径连接的两个牧场。第三个整数(范围:1..1,000,000,000)表示任意一头奶牛穿过这条路径需要的时间。"}},{"title":"输出","value":{"format":"HTML","content":"* 第1行: 假设奶牛们规划他们的路线,所有奶牛都能找到避难所所需的最短时间。如果所有奶牛都无法找到避难所,输出“-1”。"}},{"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\u003e3 4\r\n7 2\r\n0 4\r\n2 6\r\n1 2 40\r\n3 2 70\r\n2 3 90\r\n1 3 120\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e110\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\u003cbr\u003e\n\u003cbr\u003e\n在110个时间单位内,来自第1个牧场的两头奶牛可以找到该牧场的避难所,来自第1个牧场的四头奶牛可以找到第2个牧场的避难所,还有一头奶牛可以到达第3个牧场并加入到那里的奶牛一起躲在第3个牧场的避难所下。虽然还有其他计划可以让所有奶牛都找到避难所,但没有一个计划能在110个时间单位内完成。"}}]}