Maximum Throughput in a Shortest Path Network

In a computer network, routers are numbered from \(1\) to \(n\). The connectivity between routers is given together with the maximum throughput of each router (i.e. the maximum number of packets it can forward per second). Note that the throughput of the starting router \(1\) and the destination router \(n\) is not considered. There is no direct link connecting router \(1\) and router \(n\). All data packets are forwarded only along shortest paths (i.e. paths with the minimum number of hops), and the transmission delay is ignored (packets are considered to pass instantly through the network). Each intermediate router \(i\) (i.e. \(2 \le i \le n-1\)) can process at most \(c_i\) packets per second. When multiple shortest paths exist, the network can simultaneously use them as long as the throughput of each intermediate router is not exceeded.

Your task is to compute the maximum possible throughput from router \(1\) to router \(n\) under these conditions.

Note: Since the routers (except \(1\) and \(n\)) have limited throughput, if an intermediate router is used in more than one path, the total flow through that router cannot exceed its maximum throughput. To model this, you may split each intermediate router \(i\) into two nodes \(i_{in}\) and \(i_{out}\), connecting them with an edge of capacity \(c_i\). For every edge in the original network that is part of a shortest path from \(1\) to \(n\), add a directed edge from the out-node of the source router to the in-node of the destination router with infinite capacity. For router \(1\) and router \(n\), no splitting is needed.

The input guarantees that all edges are bidirectional. However, in the flow network, only those edges \((u,v)\) satisfying \(d(u) + 1 = d(v)\) (where \(d(u)\) is the shortest distance from router \(1\) to router \(u\)) are used.

Input Format Overview:

• The first line contains two integers \(n\) and \(m\) indicating the number of routers and the number of connections.
• The second line contains \(n\) integers. The \(i\)-th integer represents the maximum throughput of router \(i\) (in packets per second). For routers \(1\) and \(n\), these values are given but should be ignored.
• The next \(m\) lines each contain two integers \(u\) and \(v\), indicating that router \(u\) and router \(v\) are directly connected.

Output Format Overview:

• Output a single integer representing the maximum number of packets per second that can be forwarded from router \(1\) to router \(n\) along shortest paths.

inputFormat

The input begins with two integers, \(n\) and \(m\) (\(n \ge 3\)), separated by spaces.

The second line contains \(n\) integers where the \(i\)-th integer is the maximum throughput (in packets per second) of router \(i\). (The throughput values for routers \(1\) and \(n\) are provided but not used in the flow calculation.)

Each of the next \(m\) lines contains two integers \(u\) and \(v\) (with \(1 \le u,v \le n\) and \(u \neq v\)), indicating that there is a bidirectional connection between router \(u\) and router \(v\). It is guaranteed that there is no direct connection between router \(1\) and router \(n\).

outputFormat

Output a single integer representing the maximum throughput from router \(1\) to router \(n\), that is, the maximum number of packets per second that can be forwarded along shortest paths under the given constraints.

sample

4 4
0 5 6 0
1 2
2 3
1 3
3 4

6