牛躲雨

题目描述:

下雨了，有F (1 <= F <= 200) 个牛棚，这F个牛棚之间有P (1 <= P <= 1500)条无向边（这些边长度会给出，牛每个单位时间走一个单位的距离）。 
每个牛棚有两个值A和B（A表示一开始这个牛棚有A头牛，B表示下雨时该牛棚最多可以容纳B头牛躲雨）。问最少需要提前多少时间响下雨警告才能让所有牛在下雨前都能够找到可以遮雨的地方。

输入格式:

第1行：两个整数: F and P 
第2行至F+1行:下来F行，第i行两个整数A和B(AB的范围都是: 0..1000)描述第i个牛棚。
第F+2至F+P+1行: 下来P行，每行三个整数。X Y  L，表示牛棚X和牛棚Y之间有一条边L（ 1 <= L <= 1,000,000,000) 

输出格式:

输出一行，即为最短的时间，如果无法使得所有牛都能够有地方避雨，那么输出 "-1".

样例输入:

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

样例输出:

110

提示:

输出解释：110是最短的时间。牛棚1安排4头牛到牛棚2，牛棚1再安排1头牛走到牛棚2，再走到牛棚3 避雨。这样最少的时间就是110。

时间限制: 1000ms
空间限制: 256MB

---