#include <bits/stdc++.h> using namespace std; int main() { cin.tie(0)->sync_with_stdio(0); int n,m; cin>> n>> m; int req[n+1]; for (int i=1; i<=n; i++) cin>> req[i]; vector<vector<int>> g(n+1); for (int i=0; i<m; i++) { int u,v; cin>> u>> v; g[u].push_back(v); g[v].push_back(u); } priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq; pq.push({0, 1}); vector<int> dist(n+1, INT_MAX), rdist(n+1, INT_MAX); dist[1] = 0; while (!pq.empty()) { int u=pq.top().second, d=pq.top().first; pq.pop(); if (d > dist[u]) continue; for (auto &v : g[u]) { int add; if (req[v] > dist[u]) { add = req[v] - dist[u]; } else { add = 1; } if (dist[v] > dist[u] + add) { dist[v] = dist[u]+add; pq.push({dist[v], v}); } } } rdist[n] = 0; pq.push({0, n}); while (!pq.empty()) { int u=pq.top().second, d=pq.top().first; pq.pop(); if (d > rdist[u]) continue; for (auto &v : g[u]) { int add; if (req[v] > rdist[u]) { add = req[v] - rdist[u]; } else { add = 1; } if (rdist[v] > rdist[u] + add) { rdist[v] = rdist[u]+add; pq.push({rdist[v], v}); } } } int ans=INT_MAX; for (int i=1; i<=n; i++) { //cout<< dist[i]<< ' '<< rdist[i]<< '\n'; if (rdist[i] == dist[i]) ans = min(ans, rdist[i]*2); else ans = min(ans, max(rdist[i], dist[i])*2-1); } cout<< ans; }