Given a connected graph G with N nodes and M edges (edges are bi-directional). Every node is assigned a value A[i]. We define a value of a simple path as :
A path consists of a sequence of nodes starting with start node S and end node E.
Given a start node S and end node E, find the minimum possible "value of path" which starts with node S and ends with node E.
Input format
Output format
Print a single integer — minimum possible "value of path" between node S and E.
Constraints
1≤N≤105N−1≤M≤1061≤S,E≤NS≠E1≤u,v≤N1≤A[i]≤106
Path : 2−3−1−5 will give the minimum possible path value = 2.
Remember there can be multiple paths that give the same minimum path value between the start node and end node.