Description

Now, given the connectivity between routers in a computer network and the maximum throughput of each router (i.e., the number of packets it can forward per second), with routers numbered from $1$ to $n$, assume all packets are forwarded strictly along shortest paths. Compute the maximum throughput from router $1$ to router $n$. Ignore the time overhead of forwarding and transmission, and do not consider link bandwidth limits, i.e., assume packets can traverse the network instantaneously. Routers $1$ and $n$ serve as the source and destination, and their own throughputs are not considered. There is also no link that directly connects $1$ and $n$.

Input Format

The first line contains two integers separated by a space, representing the number of routers $n$ and the number of links $m$.

Lines $2$ to $(m + 1)$ each contain three integers $u, v, w$, indicating there is an undirected link connecting routers $u$ and $v$ with distance $w$.

Lines $(m + 2)$ to $(n + m + 1)$ each contain one integer. The integer on line $(i + m + 1)$ represents the throughput $c_i$ of router $i$.

Output Format

Output a single line containing one integer, representing the maximum throughput of the network.

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

Constraints

For $100\%$ of the testdata, it is guaranteed that $1 \leq n \leq 500$, $1 \leq m \leq 10^5$, and $1 \leq w, c_i \leq 10^9$.

Translated by ChatGPT 5