#include <iostream>
#include <algorithm>
#include <climits>
#include <string>
#include <vector>
#include <cmath>
#include <queue>
using namespace std;

#define INF 114514191

int N, K;
vector<int> path[5010];
int  cost[5010][5010];
int C[5010];
int R[5010];

int dijkstra(int dest) {
  vector<bool> used(N, false);
  vector<int> d(N, INF);
  d[0] = 0;

  while (true) {
    int v = -1;
    for (int u=0; u<N; u++) {
      if (!used[u] && (v == -1 || d[u] < d[v])) v = u;
    }
    if (v == -1) break;
    used[v] = true;

    for (int u=0; u<N; u++) {
      d[u] = min(d[u], d[v] + cost[v][u]);
    }
  }
  return d[dest];
}

void bfs(int x) {
  queue<int> q;
  q.push(x);
  q.push(0);
  vector<bool> used(N, false);
  used[x] = true;

  while (!q.empty()) {
    int s    = q.front(); q.pop();
    int dist = q.front(); q.pop();
    if (dist >= R[x]) continue;

    for (auto d : path[s]) {
      if (!used[d]) {
        q.push(d);
        q.push(dist+1);
        used[d] = true;
        cost[x][d] = C[x];
      }
    }
  }
}

int main() {
  cin >> N >> K;
  for (int i=0; i<N; i++) {
    cin >> C[i] >> R[i];
  }
  for (int i=0; i<K; i++) {
    int a, b;
    cin >> a >> b;
    path[a-1].push_back(b-1);
    path[b-1].push_back(a-1);
  }

  for (int i=0; i<N; i++) {
    for (int j=0; j<N; j++) {
      if (i == j) cost[i][j] = 0;
      else        cost[i][j] = INF;
    }
  }
  for (int i=0; i<N; i++) {
    bfs(i);
  }
  cout << dijkstra(N-1) << "\n";
  return 0;
}