#include <bits/stdc++.h>
#define int long long
#define pii pair <int , int>
#define fi first
#define se second
using namespace std;
const int INF = 1e18;
const int maxn = 2e5 + 7;
int n , m , a[maxn];
vector <int> g[maxn];
vector <int> dijkstra(int st)
{
vector <int> d(n+1 , INF);
vector <bool> vis(n+1 , false);
priority_queue <pii , vector <pii> , greater <pii>> PQ;
d[st] = 0;
PQ.push({0 , st});
while(!PQ.empty())
{
int u = PQ.top().se;
PQ.pop();
if(vis[u]) continue;
vis[u] = 1;
for(int v: g[u])
{
int neww = max(d[u] + 1 , a[v]);
if(neww < d[v])
{
d[v] = neww;
PQ.push({d[v] , v});
}
}
}
return d;
}
void solve()
{
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;
g[u].push_back(v);
g[v].push_back(u);
}
vector <int> d1 = dijkstra(1);
vector <int> dn = dijkstra(n);
int ans = INF;
for(int i = 1; i <= n; i++)
{
ans = min(ans , max(d1[i] * 2 , dn[i] * 2));
for(int v: g[i])
{
ans = min(ans , max(d1[i]*2 , dn[v]*2) + 1);
ans = min(ans , max(d1[v]*2 , dn[i]*2) + 1);
}
}
cout << ans << '\n';
}
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
solve();
return 0;
}
