#include "bits/stdc++.h"
using namespace std;
#ifdef duc_debug
#include "bits/debug.h"
#else
#define debug(...)
#endif
const int maxn = 2e5 + 5;
const int M = 4e5 + 5;
int n, m;
vector<int> g[maxn];
int a[maxn];
int d[2][maxn];
void dijkstra(int src, int d[]) {
fill(d, d + n + 1, 1e9);
using T = pair<int, int>;
priority_queue<T, vector<T>, greater<T>> pq;
pq.emplace(0, src);
d[src] = 0;
while (!pq.empty()) {
auto [dist, u] = pq.top();
pq.pop();
if (dist > d[u]) continue;
for (auto v : g[u]) {
int w = max(1, a[v] - dist);
if (d[v] > dist + w) {
d[v] = dist + w;
pq.emplace(d[v], v);
}
}
}
}
void solve() {
cin >> n >> m;
for (int i = 1; i <= n; ++i) {
cin >> a[i];
}
for (int i = 1; i <= m; ++i) {
int u, v; cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
}
dijkstra(1, d[0]);
dijkstra(n, d[1]);
int res = 2e9;
for (int i = 1; i <= n; ++i) {
res = min(res, 2 * max(d[0][i], d[1][i]));
for (auto v : g[i]) {
res = min(res, 2 * max(d[0][i], d[1][v]) + 1);
}
}
cout << res;
}
signed main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
solve();
return 0;
}
