#include<bits/stdc++.h>
using namespace std;
#define int long long
#define f first
#define s second
struct st
{
int u,w;
bool operator < (const st&o) const
{
return w>o.w;
}
};
signed main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
int n,m;
cin>>n>>m;
int a[n+1];
for(int i=1;i<=n;i++)
cin>>a[i];
vector<pair<int,int>> ad[n+1];
for(int i=0;i<m;i++)
{
int x,y;
cin>>x>>y;
ad[x].push_back({y,a[y]});
ad[y].push_back({x,a[x]});
}
int dist[n+1];
memset(dist,127,sizeof dist);
dist[1]=0;
priority_queue<st> q;
q.push({1,0});
while(!q.empty())
{
auto p=q.top();
q.pop();
int u=p.u,w=p.w;
if(dist[u]<w)
continue;
for(auto x:ad[u])
{
if(dist[x.f]>max(x.s,w+1))
{
dist[x.f]=max({x.s,w+1});
q.push({x.f,dist[x.f]});
}
}
}
int dist1[n+1];
memset(dist1,127,sizeof dist);
dist1[n]=0;
q.push({n,0});
while(!q.empty())
{
auto p=q.top();
q.pop();
int u=p.u,w=p.w;
if(dist1[u]<w)
continue;
for(auto x:ad[u])
{
if(dist1[x.f]>max(x.s,w+1))
{
dist1[x.f]=max({x.s,w+1});
q.push({x.f,dist1[x.f]});
}
}
}
int ans=LLONG_MAX;
for(int i=1;i<=n;i++)
{
ans=min(ans,max(dist[i],dist1[i])*2);
for(auto x:ad[i])
{
ans=min(ans,max(dist[i],dist1[x.f])*2+1);
ans=min(ans,max(dist1[i],dist[x.f])*2+1);
}
}
cout<<ans;
}
