#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define ppf pop_front
#define ppb pop_back
#define pf push_front
#define pb push_back
#define fr first
#define sc second
#define mnto(x,y) x = min(x, (__typeof__(x))y)
#define mxto(x,y) x = max(x, (__typeof__(x))y)
#define setval(arr, x) memset(arr, x, sizeof(arr))
int main() {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int n, m;
cin >> n >> m;
vector<ll> a(n+1);
for (int i = 1; i <= n; ++i) cin >> a[i];
vector<vector<int>> adj(n+1);
for (int i = 0; i < m; ++i) {
int u, v;
cin >> u >> v;
adj[u].pb(v);
adj[v].pb(u);
}
vector<bool> vis(n+1, 0);
vector<ll> dist1(n+1, 1e18);
dist1[1] = 0;
priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> pq;
pq.push({0, 1});
while (!pq.empty()) {
auto [d, u] = pq.top();
pq.pop();
if (vis[u]) continue;
vis[u] = 1;
for (int v : adj[u]) {
ll w = max(dist1[u]+1, a[v]);
if (dist1[v] > w) {
dist1[v] = w;
pq.push({dist1[v], v});
}
}
}
vis.assign(n+1, 0);
vector<ll> distn(n+1, 1e18);
distn[n] = 0;
pq.push({0, n});
while (!pq.empty()) {
auto [d, u] = pq.top();
pq.pop();
if (vis[u]) continue;
vis[u] = 1;
for (int v : adj[u]) {
ll w = max(distn[u]+1, a[v]);
if (distn[v] > w) {
distn[v] = w;
pq.push({distn[v], v});
}
}
}
ll ans = 1e18;
for (int u = 1; u <= n; ++u) {
mnto(ans, max(dist1[u], distn[u])<<1);
for (int v : adj[u]) {
mnto(ans, max(dist1[u], distn[v])<<1|1);
mnto(ans, max(distn[u], dist1[v])<<1|1);
}
}
cout << ans;
}
