#include <bits/stdc++.h>
using namespace std;
int main() {
cin.tie(0)->sync_with_stdio(0);
int n,m;
cin>> n>> m;
int req[n+1];
for (int i=1; i<=n; i++) cin>> req[i];
vector<vector<int>> g(n+1);
for (int i=0; i<m; i++) {
int u,v;
cin>> u>> v;
g[u].push_back(v);
g[v].push_back(u);
}
priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;
pq.push({0, 1});
vector<int> dist(n+1, INT_MAX), rdist(n+1, INT_MAX);
dist[1] = 0;
while (!pq.empty()) {
int u=pq.top().second, d=pq.top().first;
pq.pop();
if (d > dist[u]) continue;
for (auto &v : g[u]) {
int add;
if (req[v] > dist[u]) {
add = req[v] - dist[u];
}
else {
add = 1;
}
if (dist[v] > dist[u] + add) {
dist[v] = dist[u]+add;
pq.push({dist[v], v});
}
}
}
rdist[n] = 0;
pq.push({0, n});
while (!pq.empty()) {
int u=pq.top().second, d=pq.top().first;
pq.pop();
if (d > rdist[u]) continue;
for (auto &v : g[u]) {
int add;
if (req[v] > rdist[u]) {
add = req[v] - rdist[u];
}
else {
add = 1;
}
if (rdist[v] > rdist[u] + add) {
rdist[v] = rdist[u]+add;
pq.push({rdist[v], v});
}
}
}
int ans=INT_MAX;
for (int i=1; i<=n; i++) {
//cout<< dist[i]<< ' '<< rdist[i]<< '\n';
if (rdist[i] == dist[i]) ans = min(ans, rdist[i]*2);
else ans = min(ans, max(rdist[i], dist[i])*2-1);
}
cout<< ans;
}
