#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <vector>
#include <climits>

using namespace std;

#define MAX_V 5010

typedef pair<int, int> P;

struct edge{
  int to, cost;
  edge(int _to, int _cost){
    to = _to;
    cost = _cost;
  }  
};

struct node{
  int cost, mincost, v, n;
  bool operator < (const node a) const{
    return a.mincost < mincost;
  }
};

vector<int> G[MAX_V];
vector<node> Node;
vector<int> can[MAX_V];
int d[MAX_V];

int N, K;

void init(){
  for(int i = 0 ; i < MAX_V ; i++){
    G[i].clear();
  }
}

void dijkstra(int s){
  priority_queue<node> que;
  fill(d, d+MAX_V, INT_MAX);
  
  que.push(Node[0]);  
  d[s] = 0;
  
  while(!que.empty()){
    node p = que.top(); que.pop();
    int v = p.v;
    if(d[v] < p.mincost) continue;

    for(int i = 0 ; i < can[v].size() ; i++){
      int e = can[v][i];

      if(d[e] > d[v] + Node[v].cost){
	d[e] = d[v] + Node[v].cost;
	node tmp;
	tmp.v = can[v][i];
	tmp.mincost = d[e];
	que.push(tmp);
      }
    }
  }
}

vector<edge> G2[MAX_V];
int d2[MAX_V];

void dijkstra2(int s){
  priority_queue<P, vector<P>, greater<P> > que;
  
  fill(d2, d2+MAX_V, (1<<29));
  d2[s] = 0;  
  que.push(P(0, s));
  
  while(!que.empty()){
    P p = que.top(); que.pop();
    int v = p.second;
    if(d2[v] < p.first) continue;
    for(int i = 0 ; i < G2[v].size() ; i++){
      edge e = G2[v][i];
      if(d2[e.to] > d2[v] + e.cost){
	d2[e.to] = d2[v] + e.cost;
	que.push(P(d2[e.to], e.to));
      }
    }
  }  
}

int main(){
  cin >> N >> K;

  for(int i = 0 ; i < N ; i++){
    node tmp;
    tmp.v = i;
    cin >> tmp.cost >> tmp.n;
    Node.push_back(tmp);
  }  
  int from, to;
  for(int i = 0 ; i < K ; i++){
    cin >> from >> to;
    from--;
    to--;
    
    G[from].push_back(to);
    G[to].push_back(from);
    
    G2[to].push_back(edge(from, 1));
    G2[from].push_back(edge(to, 1));    
  }

  for(int i = 0 ; i < N ; i++){
    dijkstra2(i);
    for(int j = 0 ; j < N ; j++){
      if(d2[j] <= Node[i].n) can[i].push_back(j);
    }
  }
  
  dijkstra(0);
  
  
  for(int i = 0 ; i < N ; i++){
    cout << "";
  }
  cout << d[N-1] << endl;
  
  return 0;
}