P5122 [USACO18DEC] Fine Dining G

漫长的一天结束了，饥困交加的奶牛们准备返回牛棚。 农场由 $N$ 片牧场组成（$2\le N\le 5\times 10^4$），方便起见编号为 $1\dots N$。所有奶牛都要前往位于牧场 $N$ 的牛棚。其他 $N-1$ 片牧场中每片有一头奶牛。奶牛们可以通过 $M$ 条无向的小路在牧场之间移动（$1\le M\le 10^5$）。第i条小路连接牧场 $a_i$ 和 $b_i$，通过需要时间 $t_i$。每头奶牛都可以经过一些小路回到牛棚。 由于饥饿，奶牛们很乐于在他们回家的路上停留一段时间觅食。农场里有 $K$ 个有美味的干草捆，第 $i$ 个干草捆的美味值为 $y_i$。每头奶牛都想要在她回牛棚的路上在某一个干草捆处停留，但是她这样做仅当经过这个干草捆使她回牛棚的时间增加不超过这个干草捆的美味值。注意一头奶牛仅仅“正式地”在一个干草捆处因进食而停留，即使她的路径上经过其他放有干草捆的牧场；她会简单地无视其他的干草捆。

无

无

在这个例子中，牧场 $3$ 里的奶牛可以停留进食，因为她回去的时间仅会增加 $6$（从 $2$ 增加到 $8$），而这个增加量并没有超过干草捆的美味值 $7$。牧场 $2$ 里的奶牛显然可以吃掉牧场 $2$ 里的干草，因为这并不会导致她的最佳路径发生变化。对于牧场 $1$ 里的奶牛是一个有趣的情况，因为看起来她的最佳路径（$10$）可能会因为前去进食而有过大的增加量。然而，确实存在一条路径使得她可以前去干草捆处停留：先到牧场 $4$，然后去牧场 $2$（吃草），然后回到牧场 $4$。