#include <bits/stdc++.h>
using namespace std;
const int dx[]={0,1,0,-1,1,-1,-1,1};
const int dy[]={-1,0,1,0,1,1,-1,-1};
const int INF = 1<<30;
const double EPS = 1e-8;
#define PB push_back
#define mk make_pair
#define fr first
#define sc second
#define ll long long
#define reps(i,j,k) for(int i = (j); i < (k); i++)
#define rep(i,j) reps(i,0,j)
#define MOD 1000000007
#define lengthof(x) (sizeof(x) / sizeof(*(x)))
typedef pair<int,int> Pii;
typedef pair<Pii,Pii> P;
typedef vector<int> vi;
typedef vector<vi> vvi;
queue < P > Q;
vi G[5001];
int D[5001][5001];
int main(){
    int N,K;
    scanf("%d%d",&N,&K);
    rep(i,N){
        int c,r;
        scanf("%d%d",&c,&r);
        Q.push(P(Pii(c,r),Pii(i,i)));
    }
    rep(i,K){
        int s,e;
        scanf("%d%d",&s,&e);
        s--;e--;
        G[s].PB(e);
        G[e].PB(s);
    }
    fill((int *)D,(int *)(D + lengthof(D)),INF);
    
    while(!Q.empty()){
        P p = Q.front();Q.pop();
        if(p.fr.sc == 0)continue;
        rep(i,G[p.sc.sc].size()){
            if(D[p.sc.fr][G[p.sc.sc][i]] > p.fr.fr){
                D[p.sc.fr][G[p.sc.sc][i]] = p.fr.fr;
                Q.push(P(Pii(p.fr.fr,p.fr.sc-1),Pii(p.sc.fr,G[p.sc.sc][i])));
            }
        }
    }
    int d[5001];
    fill(d,d+5001,INF);
    bool used[5001];
    fill(used,used+5001,false);
    d[0] = 0;
    while(true){
        int v = -1;
        rep(u,N){
            if(!used[u] && (v == -1 || d[u] < d[v]))v = u;
        }
        if(v == -1)break;
        used[v] = true;
        rep(u,N){
            if(d[u] > d[v] + D[v][u]){
                d[u] = d[v] + D[v][u];
            }
        }
    }
    printf("%d\n",d[N-1]);
    return 0;
}