#include "bits/stdc++.h"
#define int long long
#define all(v) v.begin() , v.end()
#define sz(a) (int)a.size()
using namespace std;
const int INF = 1e18;
void _(){
int n, m;
cin >> n >> m;
int ar[n+5];
for(int i=1;i<=n;i++) cin >> ar[i];
vector<int> v[n+5];
queue<array<int,2>> q;
for(int i=1;i<=m;i++){
int a,b;
cin >> a >> b;
v[a].push_back(b);
v[b].push_back(a);
}
int dist[n+5][2005];
for(int i=0;i<n+5;i++){
for(int j=0;j<2005;j++){
dist[i][j] = INF;
}
}
q.push({1, 0});
dist[1][0] = 0;
while(!q.empty()){
auto [c, d] = q.front();
q.pop();
if(d + 1 < 2005 && dist[c][d] + 1 < dist[c][d+1]){
dist[c][d+1] = dist[c][d] + 1;
q.push({c,d+1});
}
if(d - 1 >= ar[c] && dist[c][d] + 1 < dist[c][d - 1]){
dist[c][d-1] = dist[c][d] + 1;
q.push({c,d-1});
}
for(int u : v[c]){
if(d + 1 < 2005 && d + 1 >= ar[u] && dist[c][d] + 1 < dist[u][d+1]){
dist[u][d+1] = dist[c][d] + 1;
q.push({u,d+1});
}
if(d - 1 >= ar[u] && dist[c][d] + 1 < dist[u][d - 1]){
dist[u][d-1] = dist[c][d] + 1;
q.push({u,d-1});
}
if(d >= ar[u] && dist[c][d] + 1 < dist[u][d]){
dist[u][d] = dist[c][d] + 1;
q.push({u,d});
}
}
}
cout << dist[n][0] << '\n';
}
int32_t main(){
cin.tie(0); ios::sync_with_stdio(0);
int tc=1;//cin >> tc;
while(tc--) _();
return 0;
}
