#include <iostream>
#include <vector>
#include <iomanip>
#include <map>
#include <set>
#include <numeric>
#include <queue>
#include <deque>
#include <algorithm>
#include <stack>
#include <unordered_map>
using namespace std;
using ll = long long;
int N;
bool chmin(ll&a, ll b) {
if (a > b) {
a = b;
return true;
}
return false;
}
vector<vector<int>> G;
vector<ll> A;
ll inf = (1LL << 60);
int cst(int x, int y) {
return (N * x) + y;
}
vector<pair<ll, ll> > dist(int st) {
vector<pair<ll, ll> > res(N, {inf,-1});
priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>> > pq;
pq.push({0, st});
res[st] = {0LL, A[st]};
while (!pq.empty()) {
auto tp = pq.top();
ll d = tp.first;
int v = tp.second;
pq.pop();
if (res[v].first < d) continue;
for (auto nv : G[v]) {
ll ncst = max(d + 1, A[nv]);
if (ncst < res[nv].first) {
res[nv] = {ncst, max(res[v].second, A[nv])};
pq.push({ncst, nv});
}
}
}
return res;
}
int main() {
int M;cin >> N >> M;
G.assign(N, {});
A.assign(N, 0);
for (int i = 0;i < N;i++) cin >> A[i];
for (int i = 0;i < M;i++) {
int a, b;cin >> a >>b;
a--;b--;
G[a].push_back(b);
G[b].push_back(a);
}
auto dist0 = dist(0);
auto distN = dist(N - 1);
ll res = inf;
for (int v = 0;v < N;v++) {
if (dist0[v].second == A[v] and distN[v].second == A[v]) {
//cout << v+1 << " " << dist0[v].first << " " << distN[v].first << endl;
res = min(res, dist0[v].first + distN[v].first);
}
}
cout << res << endl;
}
