#include <bits/stdc++.h>
#define int long long
int n,m;
int alt[200100];
std::vector<int> adj[200100];
int dist[3][200100];
int highest[3][200100];
int djikstra(int first,int idx){
std::priority_queue<std::pair<int,int>> pq;
for(int i=0;i<=n;i++){
dist[idx][i]=1e9;
}
pq.push({-0,first});
dist[idx][first]=0;
while(!pq.empty()){
auto weight = -pq.top().first;
//int weight = -pair
int curr = pq.top().second;
pq.pop();
for(auto to:adj[curr]){
if(dist[idx][to]>std::max(alt[to],weight+1)){
pq.push({-(std::max(alt[to],weight+1)),to});
dist[idx][to]=std::min(dist[idx][to],std::max(alt[to],weight+1));
highest[idx][to]=std::max(1+highest[idx][curr],alt[to]);
}
if(dist[idx][to]==std::max(alt[to],weight+1)){
highest[idx][to]=std::min(highest[idx][to],std::max(1+highest[idx][curr],alt[to]));
}
}
}
return 0;
}
signed main() {
std::cin >> n >> m;
for(int i=1;i<=n;i++){
int inal;
std::cin >> inal;
alt[i]=inal;
}
for(int i=0;i<m;i++){
int n1,n2;
std::cin >> n1 >> n2;
adj[n1].push_back(n2);
adj[n2].push_back(n1);
}
djikstra(1,0);
djikstra(n,1);
int min = 1e9;
for(int i=1;i<=n;i++){
int diff=std::abs(dist[0][i]-dist[1][i]);
if(std::max(highest[0][i],highest[1][i])<=std::min(dist[0][i],dist[1][i]))diff=0;
else if(highest[1][i]>dist[0][i])diff=std::min(diff,highest[1][i]-dist[0][i]);
else if(highest[0][i]>dist[1][i])diff=std::min(diff,highest[0][i]-dist[1][i]);
//int diff = (std::abs(dist[0][i]-dist[1][i]));
int tdist = dist[0][i]+dist[1][i]+std::abs(dist[0][i]-dist[1][i]);;
//there should be edgecase
//std::cout << "->" << '[' << highest[0][i] << ',' << dist[0][i] << ']' << ' '<< '[' << highest[1][i] << ','<< dist[1][i] << ']' << '\n';
min=std::min(min,tdist);
}
std::cout << min;
}
