{"trustable":false,"sections":[{"title":"","value":{"format":"HTML","content":"大农场主W拥有一个羊群,但它们在放养时会面临着野狼的威胁。为此W购入了一只牧羊犬并设置了足够安全的区域,以便所有小羊都能顺利抵达安全区。\u003c/br\u003e\n但这只牧羊犬有些顽皮,会经常带着小羊去别处玩耍,为了尽可能多的避免这种情况发生,W希望最好晚些调整羊群走向,同时在真正面对野狼时又可以给所有小羊足够的时间。\u003c/br\u003e\n这边有P(1\u003c\u003dP\u003c\u003d200)块草地供羊群啃食,并有R(1\u003c\u003dR\u003c\u003d1500)条道路连接它们。路相当宽敞,因此任意只小羊均可在任意方向穿过一条道路。\u003c/br\u003e\n农场的部分区域设有安全区,小羊可以在这里得到保护。但这些安全区规模有限,因此单个安全区或许不能容纳所有的小羊。与道路相比,安全区很小,小羊不需要时间穿过。 \u003c/br\u003e\n请计算出野狼袭击前及时疏散羊群的最短时间,给所有小羊足够的时间逃到安全区。\u003c/br\u003e"}},{"title":"Input","value":{"format":"HTML","content":"第1行:两个空格分隔的整数:P和R\u003c/br\u003e\n第2到P+1行:用于描述字段且有空格分隔的两个整数。第一个(范围0到1000)是羊群数。第二个(范围到0到1000)是安全区可容纳的小羊数量。\u003c/br\u003e\n第P+2到P+R+1行:用于描述字段且有空格分隔的三个整数。第一个和第二个整数(范围均为1到P)表示道路连接的字段。第三个整数(范围1到1000000000)是一只小羊通过过它的所需时间。\u003c/br\u003e"}},{"title":"Output","value":{"format":"HTML","content":"第1行:输出羊群进入安全区所需的最短时间。如果未能让顺利抵达则输出“-1”。"}},{"title":"Sample Input","value":{"format":"HTML","content":"\u003cpre class\u003d\"sio\"\u003e3 4\n7 2\n0 4\n2 6\n1 2 40\n3 2 70\n2 3 90\n1 3 120\u003c/pre\u003e"}},{"title":"Sample Output","value":{"format":"HTML","content":"\u003cpre class\u003d\"sio\"\u003e110\u003c/pre\u003e"}}]}