#include<bits/stdc++.h>
using namespace std;
#define int long long
#define f first
#define s second
struct st
{
int u,w,mx;
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];
set<int> ss;
for(int i=0;i<m;i++)
{
int x,y;
cin>>x>>y;
ad[x].push_back({y,max(a[x],a[y])});
ad[y].push_back({x,max(a[x],a[y])});
if(x==n)
ss.insert(y);
else if(y==n)
ss.insert(x);
}
pair<int,int> dist[n+1];
memset(dist,127,sizeof dist);
dist[1]={0,0};
priority_queue<st> q;
q.push({1,0,0});
while(!q.empty())
{
auto p=q.top();
q.pop();
int u=p.u,w=p.w,mx=p.mx;
if(dist[u].f<w||(dist[u].f==w&&dist[u].s>mx))
continue;
for(auto x:ad[u])
{
int ww;
if(mx<x.s)
{
if(dist[x.f].f>w+(x.s-mx)*2)
{
dist[x.f].f=w+(x.s-mx)*2;
dist[x.f].s=x.s;
q.push({x.f,w+(x.s-mx)*2,x.s});
}
}
else
{
if(dist[x.f].f>w+1||(dist[x.f].f==w+1&&dist[x.s].s>mx))
{
dist[x.f].f=w+1;
dist[x.f].s=mx;
q.push({x.f,w+1,mx});
}
}
}
}
int ans=LLONG_MAX;
for(auto x:ss)
{
ans=min(ans,dist[x].f);
}
cout<<ans;
}
