#include <bits/stdc++.h> using namespace std; using ll = long long; #define vi vector<long long> #define all(x) x.begin(), x.end() #define endl "\n" #define pr pair<ll, ll> #define ff first #define ss second void solution(); int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); solution(); return 0; } #define arr array<ll, 4> const int N = 2e5+10; vi adj[N]; ll a[N]; void solution() { ll n, m; cin >> n >> m; for (int i = 1; i <= n; i++) cin >> a[i]; while (m--) { int u, v; cin >> u >> v; adj[u].push_back(v); adj[v].push_back(u); } vi dist(n+1, 1e18); dist[1] = 0; priority_queue<arr> q; q.push({0, 0, 1, 1}); vi cnt(n+1); while (!q.empty()) { auto [t, h, u, p] = q.top(); q.pop(); dist[u] = min(dist[u], -t); if (cnt[u] >= 1000) continue; cnt[u]++; for (auto v : adj[u]) { if (v == p) continue; arr nxt; nxt[0] = t-1; nxt[1] = h; nxt[2] = v; nxt[3] = u; if (h < a[v] || v == n) { ll delta = abs(a[v]-h); nxt[0] -= delta-1; nxt[1] += delta; } q.push(nxt); } } cout << dist[n] << endl; }