题目描述

路由是指通过计算机网络把信息从源地址传输到目的地址的活动，也是计算机网络设计中的重点和难点。网络中实现路由转发的硬件设备称为路由器。为了使数据包最快的到达目的地，路由器需要选择最优的路径转发数据包。例如在常用的路由算法 OSPF (开放式最短路径优先) 中，路由器会使用经典的 Dijkstra 算法计算最短路径，然后尽量沿最短路径转发数据包。现在，若已知一个计算机网络中各路由器间的连接情况，以及各个路由器的最大吞吐量（即每秒能转发的数据包数量），假设所有数据包一定沿最短路径转发，试计算从路由器 $1$ 到路由器 $n$ 的网络的最大吞吐量。计算中忽略转发及传输的时间开销，不考虑链路的带宽限制，即认为数据包可以瞬间通过网络。路由器 $1$ 到路由器 $n$ 作为起点和终点，自身的吞吐量不用考虑，网络上也不存在将 $1$ 和 $n$ 直接相连的链路。

输入格式

输入文件第一行包含两个空格分开的正整数 $n$ 和 $m$，分别表示路由器数量和链路的数量。网络中的路由器使用 $1$ 到 $n$ 编号。

接下来 $m$ 行，每行包含三个空格分开的正整数 $a$、$b$ 和 $d$，表示从路由器 $a$ 到路由器 $b$ 存在一条距离为 $d$ 的双向链路。

接下来 $n$ 行，每行包含一个正整数 $c$，分别给出每一个路由器的吞吐量。

输出格式

输出一个整数，为题目所求吞吐量。

样例

7 10
1 2 2
1 5 2
2 4 1
2 3 3
3 7 1
4 5 4
4 3 1
4 6 1
5 6 2
6 7 1
1
100
20
50
20
60
1

70

数据范围与提示

对于 $100 \%$ 的数据，$n \leq 500, m \leq 100000, \ d,c \leq 10^9$