#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
const long long INF = 1e18; // Use a large value for infinity
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n;
int m;
cin >> n >> m;
vector<long long> a(n + 1);
for (int i = 1; i <= n; ++i) {
cin >> a[i];
}
vector<vector<int>> adj(n + 1);
for (int i = 0; i < m; ++i) {
int u, v;
cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
}
// --- Dijkstra 1: Calculate up[i] from source 1 ---
vector<long long> up(n + 1, INF);
priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> pq_up;
up[1] = a[1]; // Start time at region 1 is its altitude requirement (which is 0)
pq_up.push({up[1], 1});
while (!pq_up.empty()) {
long long time_u = pq_up.top().first;
int u = pq_up.top().second;
pq_up.pop();
if (time_u > up[u]) {
continue;
}
for (int v : adj[u]) {
long long new_time_v = max(time_u + 1, a[v]);
if (new_time_v < up[v]) {
up[v] = new_time_v;
pq_up.push({up[v], v});
}
}
}
// --- Dijkstra 2: Calculate down[i] from source n ---
vector<long long> down(n + 1, INF);
priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> pq_down;
down[n] = a[n]; // Start time at region n is its altitude requirement (which is 0)
pq_down.push({down[n], n});
while (!pq_down.empty()) {
long long time_v = pq_down.top().first;
int v = pq_down.top().second;
pq_down.pop();
if (time_v > down[v]) {
continue;
}
for (int u : adj[v]) { // Iterating neighbors
long long new_time_u = max(time_v + 1, a[u]);
if (new_time_u < down[u]) {
down[u] = new_time_u;
pq_down.push({down[u], u});
}
}
}
// --- Combine results to find the minimum total time ---
long long min_total_time = INF;
for (int i = 1; i <= n; ++i) {
min_total_time = min(min_total_time, up[i] + down[i]);
}
cout << min_total_time << endl;
return 0;
}
