[Usaco2005 mar]Ombrophobic Bovines 发抖的牛

约翰的牛非常害怕淋雨，仅仅想到可能被雨淋湿，就会吓得瑟瑟发抖。为了让牛群在下雨前及时撤离，约翰准备在农场安装警报器，并制定一套避雨方案。

天气预报并不总是准确。为了尽量减少误报带来的影响，约翰希望在保证所有牛都能及时进入雨棚的前提下，尽可能晚地拉响警报。

农场中共有 $F$ 块供牛吃草的田地，由 $P$ 条双向道路连接。道路足够宽，因此任意数量的牛都可以同时沿道路向任一方向通行。部分田地建有雨棚，每个雨棚能够容纳的牛数量有限。田地相对于道路很小，牛穿过田地以及进入当前田地的雨棚均不需要时间。

请计算最短的撤离时间，使每头牛都能到达某个尚有容量的雨棚。换言之，需要求出距离降雨开始至少应提前多长时间拉响警报。

输入格式

第一行包含两个以空格分隔的整数 $F$ 和 $P$，分别表示田地数量和道路数量。

接下来 $F$ 行描述各块田地。第 $i+1$ 行包含两个以空格分隔的整数，分别表示第 $i$ 块田地上的牛数和该田地中雨棚的容量。

接下来 $P$ 行描述道路。每行包含三个以空格分隔的整数 $u$、$v$ 和 $t$，表示田地 $u$ 与田地 $v$ 之间有一条双向道路，任意一头牛通过该道路所需的时间为 $t$。

输出格式

输出一个整数，表示在最优撤离方案下，所有牛进入雨棚所需的最短时间。

如果无法让所有牛都进入雨棚，输出 $-1$。

样例输入

3 4
7 2
0 4
2 6
1 2 40
3 2 70
2 3 90
1 3 120

样例输出

110

数据范围

• $1\le F\le 200$；
• $1\le P\le 1500$；
• 每块田地上的牛数均在 $0$ 到 $1000$ 之间；
• 每块田地中雨棚的容量均在 $0$ 到 $1000$ 之间；
• 对于每条道路，其两个端点编号均在 $1$ 到 $F$ 之间；
• 通过每条道路所需的时间 $t$ 满足 $1\le t\le 10^9$。

来源与许可

本题为 USACO 2005 March 试题「发抖的牛」，题面与测试数据整理自 BZOJ。

样例 1

输入

3 4
7 2
0 4
2 6
1 2 40
3 2 70
2 3 90
1 3 120

输出

110