#include <bits/stdc++.h>
using namespace std;
const int nx = 2e5 + 5;
#define ll long long
int N, M;
vector<int> adj[nx];
ll A[nx], dist1[nx], dist2[nx];
ll h1[nx], h2[nx];
ll maxH = 0;
priority_queue<tuple<ll,ll,int>, vector<tuple<ll,ll,int>>, greater<tuple<ll,ll,int>>> pq; // w, h, u
int main() {
ios_base::sync_with_stdio(0), cin.tie(0);
cin >> N >> M;
for (int i = 1; i <= N; i++) cin >> A[i], maxH = max(maxH, A[i]);
while (M--) {
int u, v;
cin >> u >> v;
adj[u].emplace_back(v);
adj[v].emplace_back(u);
}
fill(dist1, dist1 + nx, 1e18);
fill(dist2, dist2 + nx, 1e18);
dist1[1] = 0;
pq.emplace(0, 0, 1);
while (!pq.empty()) {
auto [w, h, u] = pq.top();
pq.pop();
if (dist1[u] < w) continue;
for (auto v : adj[u]) {
if (A[v] > h) {
if (dist1[v] > w + A[v] - h) {
dist1[v] = w + A[v] - h;
h1[v] = A[v];
pq.emplace(dist1[v], A[v], v);
}
} else {
if (dist1[v] > w + 1) {
dist1[v] = w + 1;
h1[v] = min(h+1, maxH);
pq.emplace(dist1[v], min(h+1, maxH), v);
}
}
}
}
dist2[N] = 0;
pq.emplace(0, 0, N);
while (!pq.empty()) {
auto [w, h, u] = pq.top();
pq.pop();
if (dist2[u] < w) continue;
for (auto v : adj[u]) {
if (A[v] > h) {
if (dist2[v] > w + A[v] - h) {
dist2[v] = w + A[v] - h;
h2[v] = A[v];
pq.emplace(dist2[v], A[v], v);
}
} else {
if (dist2[v] > w + 1) {
dist2[v] = w + 1;
h2[v] = min(h+1, maxH);
pq.emplace(dist2[v], min(h+1, maxH), v);
}
}
}
}
ll ans = 1e18;
for (int i = 2; i <= N - 1; i++) {
//cout << i << " : " << dist1[i] << " " << dist2[i] << " " << h1[i] << " " << h2[i] << endl;
if (abs(h1[i] - h2[i]) <= 1) ans = min(ans, dist1[i] + dist2[i]);
}
cout << ans;
}
