#include<iostream>
#include<queue>
#include<vector>
#include<map>
using namespace std;
#define fr first
#define sc second
typedef pair < int , int > Pi;
struct edge{
  int limit, cost;
  vector< int > node , cango;
} info[5001];
int n, k;
bool used[5001];
 
int Dijkstra(){
  priority_queue< Pi , vector< Pi > , greater< Pi > > que;
  for( que.push(Pi(0,0)) ; !que.empty() ; que.pop()){
    Pi p = que.top();
    if(used[p.sc]++) continue;
    if(p.sc == n - 1) return p.fr;
    for(int i = 0 ; i < info[p.sc].cango.size() ; i++ ){
      que.push(Pi(p.fr + info[p.sc].cost,info[p.sc].cango[i]));
    }
  }
}
int main(){
  cin >> n >> k;
  for(int i = 0 ; i < n ; i++ ){
    cin >> info[i].cost >> info[i].limit;
  }
  for(int i = 0, a, b ; i < k ; i++ ){
    cin >> a >> b;
    info[--a].node.push_back(--b);
    info[b].node.push_back(a);
  }
 
  queue< Pi > que;
  for(int i = 0 ; fill_n(used, 5001, false), i < n ; i++ ){
    for( que.push(Pi(i,info[i].limit)) ; !que.empty() ; que.pop() ){
      Pi p = que.front();
      if(!p.sc) continue;
      for(int j = 0 ; j < info[p.fr].node.size() ; j++ ){
        if(!used[info[p.fr].node[j]]++){
          info[i].cango.push_back(info[p.fr].node[j]);
          que.push(Pi(info[p.fr].node[j],p.sc-1));
        }
      }
    }
  }
  cout << Dijkstra() << endl;
}