///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; //dist - node - layer int n, m; long long a[maxN]; long long 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; } minD[1][0] = 0; int u, v; for(int i = 0; i < m; i++) { cin >> u >> v; adj[u].push_back(v); adj[v].push_back(u); } } void solve() { pq.push({{minD[1][0], 1}, 0}); while(!pq.empty()) { piii cur = pq.top(); pq.pop(); if(minD[cur.first.second][cur.second] != cur.first.first) continue; int u, v, layer; long long w; u = cur.first.second; layer = cur.second; for(int i = 0; i < adj[u].size(); i++) { v = adj[u][i]; if(layer == 0) { if(a[v] < a[u]) continue; w = max(a[v] - a[u], 1ll); } else { if(a[v] > a[u]) continue; w = max(a[u] - a[v], 1ll); } if(minD[v][layer] > minD[u][layer] + w) { minD[v][layer] = minD[u][layer]+w; pq.push({{minD[v][layer], v}, layer}); } } if(layer == 0) if(minD[u][1] > minD[u][0]) { minD[u][1] = minD[u][0]; pq.push({{minD[u][1], u}, 1}); } } cout << minD[n][1]; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); readData(); solve(); return 0; }