#include <bits/stdc++.h> #pragma GCC optimize("O3") using namespace std; using ll = long long; #define int ll const int INF = (ll)4e18; int n; vector<vector<int>> adj; vector<int> a; signed main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int m; cin >> n >> m; adj = vector<vector<int>>(n); a = vector<int>(n); for(int& i : a) cin >> i; for(int i = 0; i < m; i++) { int a,b; cin >> a >> b; a--; b--; adj[a].push_back(b); adj[b].push_back(a); } vector<int> dist(n,INF); vector<int> minA(n); priority_queue<array<int,3>, vector<array<int,3>>, greater<array<int,3>>> pq; pq.push({0,0}); while(!pq.empty()) { auto [d,mn,curr] = pq.top(); pq.pop(); if(d>dist[curr]&&mn>minA[curr]) continue; dist[curr] = min(dist[curr],max(a[curr],d)); minA[curr] = max(a[curr],mn); for(int nxt : adj[curr]) { pq.push({dist[curr]+1,minA[curr]-1,nxt}); } } cout << dist[n-1]+minA[n-1]; return 0; }