#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
vector<int> dijik(int s,int a[],vector<vector<int>> &graph,int n){
vector<int> bst(n+1);
for(int i=1;i<=n;i++){
bst[i]=1e9;
}
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> pq;
pq.push({0,s});
bst[s]=0;
while(!pq.empty()){
int u=pq.top().second,dist=pq.top().first;
pq.pop();
if(dist>bst[u]){
continue;
}
for(int v:graph[u]){
int w=max(1,a[v]-dist);
if(dist+w<bst[v]){
bst[v]=dist+w;
pq.push({bst[v],v});
}
}
}
return bst;
}
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n,m;
cin >> n >> m;
int a[n+1];
for(int i=1;i<=n;i++){
cin >> a[i];
}
vector<vector<int>> graph(n+1);
for(int i=0;i<m;i++){
int u,v;
cin >> u >> v;
graph[u].push_back(v);
graph[v].push_back(u);
}
vector<int> bst1=dijik(1,a,graph,n);
vector<int> bstn=dijik(n,a,graph,n);
int ans=1e9;
for(int u=1;u<=n;u++){
ans=min(ans,2*max(bst1[u],bstn[u]));
}
for(int u=1;u<=n;u++){
for(int v:graph[u]){
ans=min(ans,2*max(bst1[u],bstn[v])+1);
}
}
cout << ans;
}
