#include <bits/stdc++.h>
using namespace std;
const int nx = 2e5 + 5;
#define ll long long
int N, M;
vector<int> adj[nx];
ll A[nx], dist1[nx], dist2[nx];
priority_queue<pair<ll,ll>, vector<pair<ll,ll>>, greater<pair<ll,ll>>> pq; // w, h, u
int main() {
ios_base::sync_with_stdio(0), cin.tie(0);
cin >> N >> M;
for (int i = 1; i <= N; i++) cin >> A[i];
while (M--) {
int u, v;
cin >> u >> v;
adj[u].emplace_back(v);
adj[v].emplace_back(u);
}
fill(dist1, dist1 + nx, 1e18);
fill(dist2, dist2 + nx, 1e18);
dist1[1] = 0;
pq.emplace(0, 1);
while (!pq.empty()) {
auto [w, u] = pq.top();
pq.pop();
if (dist1[u] < w) continue;
for (auto v : adj[u]) {
if (dist1[v] <= max(w + 1, A[v])) continue;
dist1[v] = max(w + 1, A[v]);
pq.emplace(dist1[v], v);
}
}
dist2[N] = 0;
pq.emplace(0, N);
while (!pq.empty()) {
auto [w, u] = pq.top();
pq.pop();
if (dist2[u] < w) continue;
for (auto v : adj[u]) {
if (dist2[v] <= max(w + 1, A[v])) continue;
dist2[v] = max(w + 1, A[v]);
pq.emplace(dist2[v], v);
}
}
ll ans = 1e18;
for (int i = 1; i <= N; i++) {
//cout << i << " : " << dist1[i] << " " << dist2[i] << " \n";
ans = min(ans, 2 * max(dist1[i], dist2[i]));
}
for (int i = 1; i <= N; i++) {
for (auto v : adj[i]) ans = min(ans, 2*max(dist1[i], dist2[v]) + 1);
}
cout << ans;
}
