#include <bits/stdc++.h>
#define int long long
using namespace std;
#define pi pair<int, int>
#define ppi pair<pair<int, int>, int>
#define vi vector<int>
int n, m;
vi dijsktra(int source, vector<vi>& adj, vi& dist, vi& a) {
vi height(n, 0);
vector<int> mxHeight(n, 0);
vector<bool> vis(n, false);
set<ppi> s; // {{time spent, maximum altitude reached}, node}
s.insert({{0, 0}, source});
dist[source] = 0;
while (!s.empty()) {
pi p;
int v, t, d;
tie(p, v) = *s.begin();
tie(t, d) = p;
s.erase(s.begin());
vis[v] = 1;
for (int to : adj[v]) {
if (vis[to]) continue;
int to_time = t, to_height;
if (d < a[to]) to_height = a[to];
else to_height = d+1;
to_time += max((a[to] - d), 1ll);
if ((to_time > dist[to]) || (to_time == dist[to] && d < height[to])) continue;
s.erase({{dist[to], height[to]}, to});
dist[to] = to_time;
height[to] = to_height;
mxHeight[to] = max(mxHeight[to], max(a[to], d));
s.insert({{dist[to], height[to]}, to});
}
}
return mxHeight;
}
void solve() {
cin >> n >> m;
vector<vi> adj(n);
vi a(n);
for (int &x : a) cin >> x;
for (int i = 0; i < m; i++) {
int a, b;
cin >> a >> b;
a--;
b--;
adj[a].push_back(b);
adj[b].push_back(a);
}
vi distSource(n, INT64_MAX);
vi distEnd(n, INT64_MAX);
vi heightS = dijsktra(0, adj, distSource, a);
vi heightT = dijsktra(n-1, adj, distEnd, a);
int res = INT64_MAX;
for (int v = 0; v < n; v++) {
int cur = distSource[v] + max(distEnd[v], heightS[v]);
// cerr << v << ' ' << distSource[v] << ' ' << distEnd[v] << endl;
if (heightS[v] < heightT[v]) continue;
res = min(res, cur);
}
cout << res << endl;
}
// lets say we have a path from v to n-1.
// it can be seen that it will always be optimal to increase the height, and then at one given point start to decrease.
signed main() {
solve();
return 0;
}
