#include <bits/stdc++.h>
#define ll long long
#define state tuple<int,int,int>
#define sp << ' ' <<
#define nl << '\n'
#define cnl cout << '\n'
using namespace std;
const int nx = 2e5+5;
const int mx = 4e5+5;
const int INF = 1e9+5;
const int MOD = 1e9+7;
priority_queue<state,vector<state>,greater<state>> pq;// time , he, ci
vector<int> mp[nx];
int vs[nx][2005];
int he[mx];
int n,m;
int main(){
cin.tie(0)->sync_with_stdio(0);
cin >> n >> m;
for(int i=1;i<=n;i++)cin >> he[i];
for(int i = 0;i < m;i++){
int a,b;
cin >> a >> b;
mp[a].push_back(b);
mp[b].push_back(a);
}
vs[1][0] = 0;
pq.push({0,0,1});
while (!pq.empty()){
auto [ti,hi,ci] = pq.top();pq.pop();
//cout << ti sp hi sp ci nl;
if(ci == n && hi == 0){
cout << ti;
return 0;
}
if(vs[ci][hi]) continue;
vs[ci][hi] = 1;
if(hi > 0)pq.push({ti+1,hi-1,ci});
if(hi < 2000)pq.push({ti+1,hi+1,ci});
for(auto nci : mp[ci]){
if(hi == he[nci]-1)pq.push({ti+1,hi+1,nci});
if(hi == he[nci])pq.push({ti+1,hi,nci});
if(hi-1 == he[nci])pq.push({ti+1,hi-1,nci});
}
}
}
