#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 2e5 + 5;
int n, m, ans = LLONG_MAX, a[N], dist[N][2];
vector<int> adj[N];
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> n >> m;
for(int i = 1;i<=n;i++) cin >> a[i];
for(int i = 1;i<=m;i++){
int u, v; cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
}
memset(dist, 0x3f, sizeof dist);
dist[1][0] = 0;
pq.push({0, 1});
while(pq.size()){
auto [d, u] = pq.top();
pq.pop();
if(d > dist[u][0]) continue;
for(auto v : adj[u]){
int nd = max(1LL, a[v] - a[u]);
if(d + nd < dist[v][0]){
dist[v][0] = d + nd;
pq.push({d + nd, v});
}
}
}
dist[n][1] = 0;
pq.push({0, n});
while(pq.size()){
auto [d, u] = pq.top();
pq.pop();
if(d > dist[u][1]) continue;
for(auto v : adj[u]){
int nd = max(1LL, a[v] - a[u]);
if(d + nd < dist[v][1]){
dist[v][1] = d + nd;
pq.push({d + nd, v});
}
}
}
for(int i = 1;i<=n;i++) cout << dist[i][0] << ' ' << dist[i][1] << '\n';
for(int i = 1;i<=n;i++) ans = min(ans, 2 * max(dist[i][0], dist[i][1]));
for(int i = 1;i<=n;i++){
for(auto x : adj[i]){
ans = min(ans, 2 * max(dist[i][0], dist[x][1]) + 1);
}
}
cout << ans;
}
