#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int nmax = 2e5 + 5;
const ll inf = 1e16;
int n, m;
ll a[nmax], d[nmax];
vector <int> g[nmax];
bool dijkstra(ll t) {
for (int i=1; i<=n; i++)
d[i] = inf;
d[1] = 0;
priority_queue <pair <ll, int>, vector <pair <ll, int>>, greater<>> pq;
pq.push({0, 1});
while (!pq.empty()) {
auto [dist, u] = pq.top(); pq.pop();
if (dist>d[u]) continue;
if (u==n) return true;
for (int v : g[u]) {
ll worm = max(dist + 1, a[v]), mrow = worm - 1;
if (worm<=t-a[v] && mrow<=t-a[u] && worm<d[v]) {
d[v] = worm;
pq.push({worm, v});
}
}
}
return false;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cin >> n >> m;
for (int i=1; i<=n; i++)
cin >> a[i];
while (m--) {
int u, v; cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
}
ll l = 0, r = 4e8, ans = -1;
while (l<=r) {
ll mid = (l + r) / 2;
if (dijkstra(mid)) {
ans = mid;
r = mid - 1;
}
else l = mid + 1;
}
cout << ans;
return 0;
}
