路由是指通过计算机网络把信息从源地址传输到目的地址的活动，也是计算机网络设计中的重点和难点。网络中实现路由转发的硬件设备称为路由器。为了使数据包最快的到达目的地，路由器需要选择最优的路径转发数据包。例如在常用的路由算法 OSPF (开放式最短路径优先) 中，路由器会使用经典的 Dijkstra 算法计算最短路径，然后尽量沿最短路径转发数据包。

题目描述

现在，若已知一个计算机网络中各路由器间的连接情况，以及各个路由器的最大吞吐量（即每秒能转发的数据包数量），网络中的路由器使用 1 到 n 编号，假设所有数据包一定沿最短路径转发，试计算从路由器 1 到路由器 n 的网络的最大吞吐量。计算中忽略转发及传输的时间开销，不考虑链路的带宽限制，即认为数据包可以瞬间通过网络。路由器 1 到路由器 n 作为起点和终点，自身的吞吐量不用考虑，网络上也不存在将 1 和 n 直接相连的链路。

输入的第一行是用空格隔开的两个整数，分别代表路由器的数量 n 和链路的数量 m。

第 2 到第 (m + 1) 行，每行三个整数 u, v, w，代表存在一条连结路由器 u 和路由器 v 的距离为 w 的双向链路。

第 (m + 2) 到第 (n + m + 1) 行，每行一个整数，第 (i + m + 1) 行的整数代表路由器 i 的吞吐量 c_i。

输出一行一个整数，代表网络的最大吞吐量。

对于 100\% 的数据，保证 1 \leq n \leq 500，1 \leq m \leq 10^5，1 \leq w, c_i \leq 10^9。

重庆省选