#include<iostream>
#include<queue>
#include<vector>
#include<cstdio>

using namespace std;

struct P{int c,r;};
struct State{
  int t;
  int pos, remain;
  bool operator < (const State& st) const {
    return t > st.t;
  }
};

const int MAX = 5005;
const int INF = (1<<25);
int T[MAX][MAX];
vector<int> Edge[MAX];
P price[MAX];
int N,K;

void input(){
  scanf("%d %d",&N,&K);
  for(int i = 0; i < N; i++) scanf("%d %d",&price[i].c, &price[i].r);
  for(int i = 0; i < K; i++){
    int a,b;
    scanf("%d %d",&a, &b);
    a--;b--;
    Edge[a].push_back(b);
    Edge[b].push_back(a);
  }
}

void solve(){
  fill(T[0], T[0]+MAX*MAX, INF);
  
  T[0][0] = 0;
  priority_queue<State> Q;
  Q.push((State){0,0,0});
  while(!Q.empty()){
    const State now = Q.top();
    Q.pop();
    
    if(now.t > T[now.pos][now.remain]) continue;
    
    if(now.remain > 0){
      for(int i = 0; i < (int)Edge[now.pos].size(); i++){
	State nex = now;
	nex.pos = Edge[now.pos][i];
	nex.remain--;
	
	if(T[nex.pos][nex.remain] > nex.t){
	  T[nex.pos][nex.remain] = nex.t;
	  Q.push(nex);
	}
      }
    }
    
    State nex = now;
    nex.t += price[now.pos].c; 
    nex.remain = price[now.pos].r;
    if(T[nex.pos][nex.remain] > nex.t){
      T[nex.pos][nex.remain] = nex.t;
      Q.push(nex);
    }
  }
  
  int ans = INF;
  for(int i = 0; i < MAX; i++) ans = min(ans,T[N-1][i]);
  printf("%d\n",ans);
}

int main(){
  input();
  solve();
  return 0;
}