Routing is the activity of transmitting information from a source address to a destination address through a computer network, and it is a key focus and challenge in computer network design. Hardware devices that perform routing in a network are called routers. To ensure that data packets reach their destination as quickly as possible, routers need to select the optimal path to forward packets. For example, in the commonly used OSPF (Open Shortest Path First) routing algorithm, routers use the classic Dijkstra algorithm to calculate the shortest path and then attempt to forward data packets along the shortest path.

Now, given the connections between routers in a computer network and the maximum throughput of each router (i.e., the number of data packets it can forward per second), and assuming that all data packets must be forwarded along the shortest path, calculate the maximum network throughput from router 1 to router $n$. In the calculation, ignore the time overhead of forwarding and transmission, and do not consider link bandwidth limitations; that is, assume that data packets can pass through the network instantaneously. Router 1 and router $n$ serve as the start and end points, and their own throughput does not need to be considered. There are no direct links between 1 and $n$ in the network.

Input

The first line of the input contains two space-separated positive integers $n$ and $m$, representing the number of routers and the number of links, respectively. The routers in the network are numbered from 1 to $n$.

The next $m$ lines each contain three space-separated positive integers $a$, $b$, and $d$, representing a bidirectional link of distance $d$ between router $a$ and router $b$.

The next $n$ lines each contain a positive integer $c$, giving the throughput of each router.

Output

Output a single integer, which is the required throughput.

Examples

Input 1

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

Output 1

70

Note

The red-marked links constitute the shortest paths from 1 to 7.

Constraints

• For 30% of the data, $n \le 100$, $m \le 1000$.
• For 100% of the data, $n \le 500$, $m \le 100000$, $d, c \le 10^9$.