#include <bits/stdc++.h>
using namespace std;
#define int int64_t
signed main() {
cin.tie(0)->sync_with_stdio(0);
int n, m;
cin >> n >> m;
vector<int> a(n);
for (auto &x : a)
cin >> x;
vector<vector<int>> adj(n, vector<int>());
for (int i = 0; i < m; i++) {
int x, y;
cin >> x >> y;
x--;
y--;
adj[x].push_back(y);
adj[y].push_back(x);
}
vector<int> dist(n, INT64_MAX);
dist[0] = 0;
vector<int> ndist(n, INT64_MAX);
ndist[n - 1] = 0;
priority_queue<pair<int, int>, vector<pair<int, int>>,
greater<pair<int, int>>>
pq;
pq.emplace(0, 0);
while (!pq.empty()) {
auto [dt, s] = pq.top();
pq.pop();
for (int x : adj[s]) {
if (dist[x] > max(dt + 1, a[x])) {
dist[x] = max(dt + 1, a[x]);
pq.emplace(dist[x], x);
}
}
}
pq.emplace(0, n - 1);
while (!pq.empty()) {
auto [dt, s] = pq.top();
pq.pop();
for (int x : adj[s]) {
if (ndist[x] > max(dt + 1, a[x])) {
ndist[x] = max(dt + 1, a[x]);
pq.emplace(ndist[x], x);
}
}
}
int ans = INT64_MAX;
for (int i = 0; i < n; i++) {
ans = min(ans, max(dist[i], ndist[i]) << 1);
for (int x : adj[i]) {
ans = min(ans, max(dist[i], ndist[x]) << 1 | 1);
}
}
cout << ans << '\n';
}
