Migrated from Lutece 3193 鹤运物流

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

为了复兴金人巷，你正作为金人巷的商业顾问参与到金人巷的诸多事务之中。

金人巷拥有 $n$ 间仓库，第 $i$ 间仓库处此时有 $p_i$ 只机巧鸟，但第 $i$ 间仓库只能容纳 $q_i$ 只机巧鸟，因此并不是所有机巧鸟都可以就地回到仓库休息。

机巧鸟可以通过 $m$ 条连接各个仓库的双向道路到达其他仓库休息，通过第 $i$ 条道路的时间是 $t_i$ 。机巧鸟很小，因此不需要考虑堵塞的情况。

为了让机巧鸟早些休息，你现在需要告诉它们，至少需要多少时间才可以让所有机巧鸟进入仓库休息。如果无论如何都无法使某些机巧鸟回到仓库休息，则输出 $-1$。

Input

第一行两个整数 $n$ 和 $m$ ，分别表示仓库数量和道路数量。

接下来 $n$ 行，每行两个整数 $p_i$ 和 $q_i$ ，分别表示第 $i$ 间仓库此时的机巧鸟数量和可以容纳的机巧鸟数量。

再接下来 $m$ 行，每行三个整数 $u_i$ , $v_i$ 和 $t_i$ ，分别表示第 $i$ 条道路连接的两个仓库和机巧鸟通过这条路所需要的时间。

Output

一个整数，表示让所有机巧鸟回到仓库的最少时间。

Samples

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

110

Constraints

$1 \leq n \leq 200$

$1 \leq m \leq 1500$

$1 \leq p_i,q_i \leq 1000$

$1 \leq u_i,v_i \leq n$

$1 \leq t_i \leq 10^9$

数据可能存在重边和自环。

Resources

2024 UESTC ICPC Training for Graph