#include <bits/stdc++.h>
using namespace std;
#define print(l) for(auto i:l) cout<<i<<" ";cout<<endl;
#define input(t,l,n) vector<t>l(n);for(int i = 0;i<n;i++)cin>>l[i];
#define int long long
#define pb push_back
#define all(l) l.begin(),l.end()
#define pii pair<int,int>
#define fi first
#define se second
const int M = 1e9+7;
const int inf = (int)1e18;
void io(){
#ifndef ONLINE_JUDGE
freopen("input.in","r",stdin);
#endif
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cout << fixed<<setprecision(9);
}
vector<vector<vector<int>>> adj;
vector<int> co;
int ans = inf;
int n , m;
priority_queue<vector<int>> pq;
void process_pq(){
while(!pq.empty()){
auto top = pq.top(); pq.pop();
int ccost = -top[0];
int u = top[1];
int al = top[2];
int canin = top[3];
int inde = top[4];
if(co[u] < ccost) continue;
for(auto &x : adj[u]){
int v = x[0];
int ral = x[1];
int acos = 0;
int ncanin = canin;
int ninde = inde;
if(ral > al){
int delta = ral - al - 1;
int use = min(delta, ncanin);
delta -= use; ncanin -= use;
use = min(delta, ninde);
delta -= use; ninde -= use;
acos += delta;
if(co[v] >= co[u] + acos + 1){
co[v] = co[u] + acos + 1;
if(v == n){
// arriving at region n; need to ensure landing height 0 accounted separately
ans = min(ans, co[v] + max(0ll, al - ninde));
}
pq.push({-co[v], v, ral, ncanin + ninde, 0});
}
}
else if(ral == al){
ncanin++;
if(co[v] >= co[u] + acos + 1){
co[v] = co[u] + acos + 1;
if(v == n){
ans = min(ans, co[v]);
}
pq.push({-co[v], v, ral, ncanin + ninde, 0});
}
}
else { // ral < al (descent)
ninde++;
// amount we can use from ninde to lower altitude difference
int used = min(ninde, al - ral);
ninde -= used;
// x2 is the number used to close the gap; leftover (ninde) remains for other uses
int x2 = used;
if(co[v] >= co[u] + acos + 1){
co[v] = co[u] + acos + 1;
if(v == n){
ans = min(ans, co[v] + max(0ll, al - ninde));
}
// IMPORTANT: new altitude must be ral (region v's required minimum)
pq.push({-co[v], v, ral, ncanin + x2, ninde});
}
}
}
}
}
void solve(int testcase_number){
cin>>n>>m;
adj.clear();
adj.resize(n+1);
co.clear();
co.resize(n+1, inf);
co[1] = 0;
input(int, l, n); // l holds a[1..n]
for(int i = 0;i<m;i++){
int u,v; cin>>u>>v;
adj[u].pb({v, l[v-1]});
adj[v].pb({u, l[u-1]});
}
while(!pq.empty()) pq.pop();
pq.push({0,1,0,0,0});
process_pq();
if(ans == inf) cout << "-1\n";
else cout << ans << "\n";
}
signed main(){
// io();
int t = 1;
for(int i = 1;i<=t;i++){
solve(i);
}
return 0;
}
