#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define FOR(i, l, r) for(int i = l; i <= r; i++)
#define FORD(i, l, r) for(int i = l; i >= r; i--)
#define db double
#define ldb long double
#define all_1(x) (x).begin(), (x).end()
#define all(x) (x).begin(), (x).end()
#define ins insert
#define pb push_back
const int N = 2e5 + 5;
int n, m;
ll a[N];
vector<int> adj[N];
vector<ll> dijkstra(int source){
vector<ll> dist(n + 1, 2e18);
priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> pq;
pq.push({0, source});
dist[source] = 0;
while(!pq.empty()){
auto [dist_u, u] = pq.top();
pq.pop();
if(dist_u != dist[u]) continue;
for(int v : adj[u]){
ll cand = max(dist[u] + 1, a[v]);
if (dist[v] > cand) {
dist[v] = cand;
pq.push({dist[v], v});
}
}
}
return dist;
}
void solve(){
cin >> n >> m;
FOR(i, 1, n) cin >> a[i];
FOR(i, 1, m){
int u, v;
cin >> u >> v;
adj[u].pb(v);
adj[v].pb(u);
}
vector<ll> dist1 = dijkstra(1);
vector<ll> dist2 = dijkstra(n);
//dist1: 1 -> i, dist2: n -> i
ll ans = 2e18;
FOR(i, 1, n){
ans = min(ans, 2ll * max(dist1[i], dist2[i]));
}
FOR(u, 1, n){
for(int v : adj[u]){
ans = min(ans, 2ll * max(dist1[u], dist2[v]) + 1);
}
}
cout << ans << "\n";
}
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
int t = 1;
//cin >> t;
while(t--){
solve();
}
return 0;
}
