#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define f first
#define s second
#define sz(a) (int)((a).size())
#define all(a) (a).begin(), (a).end()
#define uni(a) sort(all(a)), (a).resize(unique(all(a)) - (a).begin())
typedef tuple <int, int, int> tp;
typedef pair <int, int> ii;
const int N = 2e3 + 10;
int n, m, a[N], mx;
priority_queue <tp, vector <tp>, greater <tp>> pq;
vector <int> graph[N];
unordered_map <int, ll> f[N];
void solve() {
cin >> n >> m;
for (int i = 1; i <= n; i++) {
cin >> a[i];
mx = max(mx, a[i]);
}
for (int i = 1; i <= m; i++) {
int u, v;
cin >> u >> v;
graph[u].push_back(v);
graph[v].push_back(u);
}
f[1][0] = 0;
pq.push({0, 1, 0});
while (sz(pq)) {
ll w, u, i; tie(w, u, i) = pq.top(); pq.pop();
if (w > f[u][i]) continue;
for (int v : graph[u]) {
if (i >= a[v]) {
if (!f[v].count(i)) f[v][i] = 1e18;
if (f[v][i] > f[u][i] + 1) {
f[v][i] = f[u][i] + 1;
pq.push({f[v][i], v, i});
}
}
if (i < mx && i + 1 >= a[v]) {
if (!f[v].count(i + 1)) f[v][i + 1] = 1e18;
if (f[v][i + 1] > f[u][i] + 1) {
f[v][i + 1] = f[u][i] + 1;
pq.push({f[v][i + 1], v, i + 1});
}
}
if (i > 0 && i - 1 >= a[v]) {
if (!f[v].count(i - 1)) f[v][i - 1] = 1e18;
if (f[v][i - 1] > f[u][i] + 1) {
f[v][i - 1] = f[u][i] + 1;
pq.push({f[v][i - 1], v, i - 1});
}
}
if (i < a[v]) {
if (!f[v].count(a[v])) f[v][a[v]] = 1e18;
if (f[v][a[v]] > f[u][i] + a[v] - i) {
f[v][a[v]] = f[u][i] + a[v] - i;
pq.push({f[v][a[v]], v, a[v]});
}
}
}
if (i < mx) {
if (!f[u].count(i + 1)) f[u][i + 1] = 1e18;
if (f[u][i + 1] > f[u][i] + 1) {
f[u][i + 1] = f[u][i] + 1;
pq.push({f[u][i + 1], u, i + 1});
}
}
if (i > 0) {
if (!f[u].count(i - 1)) f[u][i - 1] = 1e18;
if (f[u][i - 1] > f[u][i] + 1) {
f[u][i - 1] = f[u][i] + 1;
pq.push({f[u][i - 1], u, i - 1});
}
}
}
cout << f[n][0] << '\n';
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
// freopen("airplane.inp", "r", stdin);
// freopen("airplane.out", "w", stdout);
int t = 1;
// cin >> t;
while (t--) {
solve();
}
return 0;
}
