Description

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

Input Format

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

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

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

Output Format

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

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

Hint

数据规模与约定

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