• [I] 嘛~寝室寝室！

  • 时间限制: 2000 ms　内存限制: 65535 K
  • 问题描述
  • 啦啦啦~集训终于开始了（虽然你们看到这道题目的时候集训已经要结束了）！！但是由于东西校区的缘故，在东校区的孩子不得不跑到西校区来，于是如何分配寝室就成了一个问题。由于集训的人数多，寝室提供的数量又不多，于是我们必须赶在其它“XXX”孩子住进去之前先住进去。
  • 输入
  • 第一行输如N（1<=N<=300）,M（1<=M<=1500）。分别代表学校提供了N个寝室楼，M条路径连接寝室楼。
    接下来有N行，每行两个数A（1<= A <= 1000）,B（1 <= B <= 1000）。分别代表第i个寝室楼（第i行）里，已经在了A个同学，这栋寝室楼里只提供B个寝室。
    在接下来M行，每行三个数x，y，z（1<= z <= 1,000,000,000）。表示从第x栋楼去第y栋楼所需z分钟，当然从y到x也需要z分钟。
    输入到文件尾结束。
  • 输出
  • 输出所有集训队的孩子分配好住的地方需要最短的时间。如果不能分配到寝室，输出-1。
  • 样例输入
  • 4 6
8 3
4 5
0 9
3 4
1 3 120
2 4 10
1 2 70
2 3 20
2 1 50
3 4 90
4 6
9 3
4 5
0 9
3 4
1 3 120
2 4 10
1 2 70
2 3 20
2 1 50
3 4 90
  • 样例输出
  • 50
60
  • 提示
  • 无
  • 来源
  • Minary
  • 操作

显示春菜