#include <bits/stdc++.h>
using namespace std;
#define int long long
#define MAX_N 200010
#define INF 200000000000000
int a[MAX_N];
vector<int> adj[MAX_N];
unordered_map<int,int> dist[MAX_N];
int highestSeen[MAX_N];
struct P {
int dest, dist, height;
bool operator< (P other) const {
return dist > other.dist;
}
};
signed main(){
int n,m; cin >> n >> m;
for(int i=1;i<=n;i++) cin >> a[i];
for(int i=0;i<m;i++){
int u,v; cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
}
fill(highestSeen,highestSeen+n+5,-1);
priority_queue<P> todo;
todo.push({1,0,0});
while(!todo.empty()){
P u = todo.top(); todo.pop();
if (u.height > highestSeen[u.dest]){
highestSeen[u.dest] = u.height;
dist[u.dest][u.height] = u.dist;
if (u.dest==n) continue;
for(auto v : adj[u.dest]){
// do not change height if legal
if (u.height >= a[v]) todo.push({v,u.dist+1,u.height});
// drop height if legal
if (u.height-1 >= a[v]) todo.push({v,u.dist+1,u.height-1});
// raise height to at least a[v]-1, then increase
int lift = max((int)1, a[v]-u.height);
todo.push({v, u.dist+lift,u.height+lift-1});
}
}
}
int res = INF;
for(auto [a,b] : dist[n]){
res = min(res, a+b);
}
cout << res << '\n';
return 0;
}
