#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fi first
#define se second
const ll M=1e9+7;
ll n,m,u,v;
ll a[200005],f1[200005],f2[200005];
vector<ll> e[200005];
vector<pair<ll,ll>> p;
int main() {
ios_base::sync_with_stdio(0);cin.tie(0);
cin>>n>>m;
for (ll i=1;i<=n;i++) {
cin>>a[i];
f1[i]=-1;
f2[i]=-1;
}
for (ll i=1;i<=m;i++) {
cin>>u>>v;
p.push_back({u,v});
e[u].push_back(v);
e[v].push_back(u);
}
priority_queue<pair<ll,ll>,vector<pair<ll,ll>>,greater<pair<ll,ll>>> pq;
pq.push({0,1});
while(!pq.empty()) {
auto [v,id]=pq.top();
pq.pop();
if (f1[id]!=-1) continue;
f1[id]=v;
for (ll i=0;i<e[id].size();i++) {
if (f1[e[id][i]]!=-1) continue;
ll cost=max((ll)1,a[e[id][i]]-v);
pq.push({v+cost,e[id][i]});
}
}
pq.push({0,n});
while(!pq.empty()) {
auto [v,id]=pq.top();
pq.pop();
if (f2[id]!=-1) continue;
f2[id]=v;
for (ll i=0;i<e[id].size();i++) {
if (f2[e[id][i]]!=-1) continue;
ll cost=max((ll)1,a[e[id][i]]-v);
pq.push({v+cost,e[id][i]});
}
}
ll res=1e18;
for (ll i=1;i<=n;i++) {
// cout<<f1[i]<<" "<<f2[i]<<endl;
res=min(res,max(f1[i],f2[i])*2);
}
for (ll i=0;i<m;i++) {
auto[x,y]=p[i];
res=min(res,max(f1[x],f2[y])*2+1);
res=min(res,max(f2[x],f1[y])*2+1);
}
cout<<res;
}
