///TRAN THAI BAO :3
#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
using namespace std;
#define maxN 200007
#define oo 1e18
typedef pair<long long, long long> pii;
typedef pair<pii, long long> piii;
int n, m;
long long a[maxN];
pii minD[maxN][2];
vector<int>adj[maxN];
priority_queue<piii, vector<piii>, greater<piii> >pq;
void readData()
{
cin >> n >> m;
for(int i = 1; i <= n; i++)
{
cin >> a[i];
minD[i][0] = minD[i][1] = {oo, 0};
}
int u, v;
for(int i = 0; i < m; i++)
{
cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
}
}
bool better(pii x, pii y) //x > y
{
if(x.first != y.first)
return x.first < y.first;
return x.first > y.first;
}
void dijkstraFrom(int root, int layer)
{
minD[root][layer] = {0, 0};
pq.push({minD[root][layer], root});
pii newD;
while(!pq.empty())
{
piii cur = pq.top();
pq.pop();
if(minD[cur.second][layer] != cur.first)
continue;
int u = cur.second;
int curH = minD[u][layer].second;
for(int i = 0; i < adj[u].size(); i++)
{
int v = adj[u][i];
long long w = max(a[v]-curH, 1ll);
newD = minD[u][layer];
newD.first += w;
newD.second = max(newD.second+1, a[v]);
if(better(newD, minD[v][layer]))
{
minD[v][layer] = newD;
pq.push({minD[v][layer], v});
}
}
}
}
void solve()
{
long long ans = oo;
for(int i = 1; i <= n; i++)
ans = min(ans, minD[i][0].first + minD[i][1].first + max(abs(minD[i][0].second - minD[i][1].second)-1, 0ll));
cout << ans;
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
readData();
dijkstraFrom(1, 0);
dijkstraFrom(n, 1);
solve();
return 0;
}
