#P2402. 奶牛隐藏

奶牛隐藏

题目背景

这本是一个非常简单的问题,然而奶牛们由于下雨已经非常混乱,无法完成这一计算,于是这个任务就交给了你。(奶牛混乱的原因看题目描述)

题目描述

在一个农场里有 nn 块田地。某天下午,有一群牛在田地里吃草,他们分散在农场的诸多田地上,农场由 mm 条无向的路连接,每条路有不同的长度。

突然,天降大雨,奶牛们非常混乱,想要快点去躲雨。已知每个田地都建立有一个牛棚,但是每个牛棚只能容纳一定数量的牛躲雨,如果超过这个数量,那多出的牛只能去别的田地躲雨。奶牛们每移动 11 的距离花费 11 时间,奶牛们想知道它们全部都躲进牛棚,最少需要多少时间。(即最后一头奶牛最少要花多久才能躲进牛棚)。

输入格式

第一行有两个整数,分别代表田地数 nn 和道路数 mm

接下来 nn 行,每行两个整数,第 (i+1)(i + 1) 行的整数 si,pis_i, p_i 分别表示第 ii 块田地的牛的数量以及该田地的牛棚最多可以容纳多少牛。

接下来 mm 行,每行三个整数 u,v,wu, v, w,代表存在一条长度为 ww 的连接 uuvv 的道路。

输出格式

输出一行一个整数表示所有奶牛全都躲进牛棚所用的最少时间。如果无法使全部奶牛都躲进牛棚,输出 1-1

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

提示

样例输入输出 1 解释

11 号点的两只牛直接躲进 11 号牛棚,剩下的 55 只中,44 只跑去 22 号点,还有一只沿 1231 \to 2 \to 3 躲进 33 号点, 33 号点的 22 只牛也直接躲进去,这样最慢的牛花费的时间是 110110

数据规模与约定

对于 100%100\% 的数据,保证:

  • 1n2001 \leq n \leq 2001m15001 \leq m \leq 1500
  • 1u,vn1 \leq u, v \leq n1w10151 \leq w \leq 10^{15}1si,pi10161 \leq s_i, p_i \leq 10^{16}