题目描述

FJ 的牛们非常害怕淋雨，那会使他们瑟瑟发抖。他们打算安装一个下雨报警器，并且安排了一个撤退计划。他们需要计算最少的让所有牛进入雨棚的时间。
牛们在农场的 $F$ 个田地上吃草。有 $P$ 条双向路连接着这些田地。路很宽，无限量的牛可以通过。田地上有雨棚，雨棚有一定的容量，牛们可以瞬间从这块田地进入这块田地上的雨棚。
请计算最少的时间，让每只牛都进入雨棚。

输入格式

第 $1$ 行：两个整数 $F$ 和 $P$；
第 $2$ 到 $F+1$ 行：第 $i+1$ 行有两个整数描述第 $i$ 个田地，第一个表示田地上的牛数，第二个表示田地上的雨棚容量。两个整数都在 $0$ 和 $1000$ 之间。
第 $F+2$ 到 $F+P+1$ 行：每行三个整数描述一条路，分别是起点终点，及通过这条路所需的时间（在 $1$ 和 $10^9$ 之间）。

输出格式

一个整数，表示最少的时间。如果无法使牛们全部进入雨棚，输出 $-1$。

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

110

提示

对于 $100\%$ 的数据：$1\le F\le 200$，$1\le P\le 1500$。