#include<bits/stdc++.h>
#define int long long
#define PB push_back
#define MP make_pair
#define FI first
#define SE second
using namespace std ;
static const int INF = 1e9;
static const int MAX_N = 1e+6 +10;
typedef pair<int,int> pii;

struct edge{
    int to,cost;
    edge(){}
    edge(int p1,int p2){
        to=p1;
        cost=p2;
    }
};

int N,K;
vector<int> V[5010];
pii G[6010];
vector<int> D[5010];
int d[6010];
int A[6010];

void bfs(int s){
    for(int i=0;i<6000;++i)d[i]=INF;
    queue<pii> que;
    que.push(pii(s,0));
    while(!que.empty()){
        pii p=que.front();
        que.pop();
        int v = p.FI;
        if(d[v]==1)continue;
        d[v]=1;
        if(p.SE<=G[s].SE&&p.FI!=s){
             D[s].PB(v);
        }
        for(int i=0;i<V[v].size();++i){
             que.push(pii(V[v][i],p.SE+1));
        }
     }
}

void dijkstra(int s){
    priority_queue<pii,vector<pii>,greater<pii> > que;
    for(int i=0;i<6000;++i)A[i]=INF;
    A[s]=0;
    que.push(pii(0,s));
    while(!que.empty()){
        pii p = que.top();
        que.pop();
        int v=p.SE;
        if(A[v]<p.FI)continue;
        for(int i=0;i<V[v].size();i++){
            int e = V[v][i];
            if(A[e]>A[v]+G[v].FI){
                A[e] = A[v]+G[v].FI;
                que.push(pii(A[e],e));
            }
        }
    }
}

signed main(){
    cin>>N>>K;
    for(int i=0;i<N;++i){
        cin>>G[i].FI>>G[i].SE;
    }
    for(int i=0;i<K;++i){
        int a,b;
        cin>>a>>b;
        a--;b--;
        V[a].PB(b);
        V[b].PB(a);
    }
    for(int i=0;i<N-1;++i)bfs(i);
    for(int i=0;i<N-1;++i){
        V[i].clear();
    }
    for(int i=0;i<N-1;++i){
        for(int j=0;j<D[i].size();++j){
            int a=i;
            int b=D[i][j];
            V[a].PB(b);
        }
    }
    dijkstra(0);
    cout<<A[N-1]<<endl;
}