// programming contest template

#include <cstdio>
#include <algorithm>
#include <functional>
#include <vector>
#include <queue>
#include <map>

using namespace std;

#define MAX_N 5050
#define MAX_K 10010
#define INF 1001001001 
int N, K;
struct Taxi {
    int R;
    int C;
};
Taxi taxis[MAX_N];
// ??£??\???????????????
//int M[MAX_N][MAX_N] = {0};

vector<int> G[MAX_N];
struct edge { int to, cost; };
vector<edge> G2[MAX_N];
typedef pair<int, int> P;
int bfs(int);
void Dijkstra();
int d[MAX_N];
int d2[MAX_N];

int main() {
    scanf("%d %d", &N, &K);
    for (int i = 1; i <= N; i++) {
        scanf("%d %d", &taxis[i].C, &taxis[i].R);
    }
    
    //printf("%d %d\n", N, K);
    int from, to;
    for (int k = 1; k <= K; k++) {
        scanf("%d %d", &from, &to);
   //     printf("%d %d\n", from, to);
        G[from].push_back(to);
        G[to].push_back(from);

        // from ??¨ to ??? 1????????§??????
        // G[0] ??????
        // G[1] [0][1][2] 
        // G[2] [0][1][2]
        //
        // G[0]????????????vector???1-origin
    }
    
   // printf("------------\n");
   // for (int i = 1; i <= N; i++) {
   //     printf("%d:", i);
   //     for (int j = 1; j <= G[i].size(); j++) {
   //         printf("%d ", G[i][j-1]); 
   //     }
   //     printf("\n");
   // }

    for (int i = 1; i <= N; i++) {
        bfs(i);
    }



   // for (int i = 1; i <= N; i++) {
   //     for (int j = 1; j <= G2[i].size(); j++) {
   //         printf("%5d", G2[i][j-1].cost);
   //     }
   //     printf("\n");
   // }

   // for (int i = 0; i < N+1; i++) {
   //     printf("d[%d]:%d d2[%d]:%d\n", i, d[i], i, d2[i]);
   // }

    Dijkstra();
    printf("%d\n", d[N]);
    return 0;
}



int bfs(int s){
    //printf("s:%d --------------\n", s);
    //for (int i = 0; i < G[s].size(); i++) {
    //    printf("G[%d][%d]:%d\n", s, i, G[s][i]);
    //}
    queue<int> q;

    q.push(s);
    for (int i = 1; i <= N; i++) {
        d2[i] = INF;
    }
    d2[s] = 0;
    int u;
    while ( !q.empty() ) {
        u = q.front(); q.pop();
        for (int i = 1; i <= G[u].size(); i++) {
            int to = G[u][i-1];
            if ( d2[to] == INF) {
                if (d2[u] + 1 <= taxis[s].R) {
                    //cost[s][to] = taxis[s].C;
                    d2[to] = d2[u] + 1;
                    edge e = { to, taxis[s].C };
     //               printf("to:%d, cost:%d\n", to, taxis[s].C);
                    G2[s].push_back(e);
                    q.push(to);
                } else {
                    continue;
                }
            }
        }
    }

    //for (int i = 0; i < N; i++) {
    //    printf("d2[%d]:%d\n", i+1, d2[i+1]);
    //}

}


void Dijkstra(){
    priority_queue<P, vector<P>, greater<P> > que;
    for (int i = 0; i <= N; i++) {
        d[i] = INF;
    }
    d[1] = 0;

    //printf("d[N]:%d\n", d[N]);
    que.push(P(0, 1));

    while (!que.empty()) {
        P p = que.top(); que.pop();
        int v = p.second;
        if (d[v] < p.first) {
            continue;
        }
        for (int i = 0; i < G2[v].size(); i++) {
            edge e = G2[v][i];
            if (d[e.to] > d[v] + e.cost) {
                d[e.to] = d[v] + e.cost;
                que.push(P(d[e.to], e.to));
            }
        }
    }


}

Measured memory_bytes: 125832