///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; int n, m; long long a[maxN]; long long minD[maxN][2]; vector<int>adj[maxN]; priority_queue<pii, vector<pii>, greater<pii> >pq; void readData() { cin >> n >> m; for(int i = 1; i <= n; i++) { cin >> a[i]; minD[i][0] = minD[i][1] = oo; } int u, v; for(int i = 0; i < m; i++) { cin >> u >> v; adj[u].push_back(v); adj[v].push_back(u); } } void dijkstraFrom(int root, int layer) { minD[root][layer] = 0; pq.push({minD[root][layer], root}); while(!pq.empty()) { pii cur = pq.top(); pq.pop(); if(minD[cur.second][layer] != cur.first) continue; int u = cur.second; for(int i = 0; i < adj[u].size(); i++) { int v = adj[u][i]; long long w = max(abs(a[v]-a[u]), 1ll); if(minD[v][layer] > minD[u][layer]+w) { minD[v][layer] = minD[u][layer]+w; pq.push({minD[v][layer], v}); } } } } void solve() { long long ans = oo; for(int i = 1; i <= n; i++) //chon peak ans = min(ans, minD[i][0] + minD[i][1]); 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; }