【题意】

下雨了，有 $N (1 \le N \le 200)$ 个牛棚，这 $N$ 个牛棚之间有 $M(1 \le M \le 1500)$ 条无向边。给出这些边长度，牛每个单位时间走一个单位的距离。

每个牛棚有两个值 $A_i$ 和 $B_i$（ $A_i$ 表示一开始这个牛棚有 $A_i$ 头牛，$B_i$ 表示下雨时该牛棚最多可以容纳 $B_i$ 头牛躲雨）。

问最少需要提前多少时间响下雨警告才能让所有牛在下雨前都能够找到可以遮雨的地方。

【输入格式】

第一行两个整数: $N , M$

下来 $N$ 行，每行两个整数 $A_i$ 、$B_i$ ($0 \le A_i,B_i \le 1000$)。

下来 $M$ 行，每行三个整数 $x,y,c$，表示牛棚 $x$ 和牛棚 $y$ 之间有一条长度为 $c(1 \le c \le 10^9)$ 的无向边。

【输出格式】

输出一行，即为最短的时间，如果无法使得所有牛都能够有地方避雨，那么输出 "-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。