///TRAN THAI BAO :3 #include <iostream> #include <cstdio> #include <vector> #include <queue> using namespace std; #define maxN 200007 #define oo 1e18 typedef pair<long long, long long> pii; typedef pair<pii, long long> piii; int n, m; long long a[maxN]; pii minD[maxN][2]; vector<int>adj[maxN]; priority_queue<piii, vector<piii>, greater<piii> >pq; void readData() { cin >> n >> m; for(int i = 1; i <= n; i++) { cin >> a[i]; minD[i][0] = minD[i][1] = {oo, 0}; } int u, v; for(int i = 0; i < m; i++) { cin >> u >> v; adj[u].push_back(v); adj[v].push_back(u); } } bool better(pii x, pii y) //x > y { if(x.first != y.first) return x.first < y.first; return x.first > y.first; } void dijkstraFrom(int root, int layer) { minD[root][layer] = {0, 0}; pq.push({minD[root][layer], root}); pii newD; while(!pq.empty()) { piii cur = pq.top(); pq.pop(); if(minD[cur.second][layer] != cur.first) continue; int u = cur.second; int curH = minD[u][layer].second; for(int i = 0; i < adj[u].size(); i++) { int v = adj[u][i]; long long w = max(a[v]-curH, 1ll); newD = minD[u][layer]; newD.first += w; newD.second = max(newD.second+1, a[v]); if(better(newD, minD[v][layer])) { minD[v][layer] = newD; pq.push({minD[v][layer], v}); } } } } void solve() { long long ans = oo; for(int i = 1; i <= n; i++) ans = min(ans, minD[i][0].first + minD[i][1].first + max(abs(minD[i][0].second - minD[i][1].second)-1, 0ll)); cout << ans; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); readData(); dijkstraFrom(1, 0); dijkstraFrom(n, 1); solve(); return 0; }