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