#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 2e5 + 5, inf = 1e18 + 5;
vector<int> adj[maxn];
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int n, m; cin >> n >> m;
vector<int> a(n + 1);
for(int i = 1; i <= n; i++) cin >> a[i];
auto dijk = [&](int s) -> vector<int> {
vector<int> d(n + 1, inf);
d[s] = 0;
priority_queue<pair<int, int>> pq;
pq.push({0, s});
while(!pq.empty()){
auto [dist, u] = pq.top();
pq.pop();
if(-dist != d[u]) continue;
for(int v: adj[u]){
int nxt = max(-dist + 1, a[v]);
if(d[v] > nxt){
d[v] = nxt;
pq.push({-d[v], v});
}
}
}
return d;
};
for(int i = 1; i <= m; i++){
int u, v; cin >> u >> v;
adj[v].push_back(u);
adj[u].push_back(v);
}
vector<int> d1 = dijk(1), dn = dijk(n);
int ans = inf;
for(int u = 1; u <= n; u++){
ans = min(ans, max(d1[u], dn[u]) * 2);
for(int v: adj[u]){
ans = min(ans, max(d1[u], dn[v]) * 2 + 1);
ans = min(ans, max(d1[v], dn[u]) * 2 + 1);
}
}
cout << ans;
}
