#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int N,K;
int C[5555],R[5555];
vector<int> G[5555];
struct state{
  int id, c;
  bool operator<( const state &st ) const {
    return c > st.c; 
  }
};
vector<int> nG[5555];

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

void bfs(int st){
  queue<state> q;
  vector<int> h(N,-1);
  q.push( (state){ st, 0 } );
  h[st] = 0;
  while( !q.empty() ){
    state p = q.front(); q.pop();
    if( p.c >= R[st] ) break;
    int nc = p.c + 1;
    for(int to : G[p.id]) {
      if( h[to] == -1 ){
	h[to] = nc;
	q.push( (state){ to, nc } );
	nG[st].push_back( to );
      }
    }
  }
}

const int INF = 1000000009;
int dijk(int st){
  priority_queue<state> q;
  vector<int> h(N,INF);  
  q.push( (state){ st, 0 } );
  h[st] = 0;
  while( !q.empty() ){
    state p = q.top(); q.pop();
    if( h[p.id] < p.c ) continue;
    if( p.id == N-1 ) return h[p.id];
    int nc = p.c + C[p.id];
    for(int to : nG[p.id]){
      if( h[ to ] > nc ) {
	h[ to ] = nc;
	q.push( (state){ to, nc } );
      }
    }
  }
  return h[N-1];
}

int main(){
  while( cin >> N >> K && (N||K) ) {
    init();
    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; --a; --b;
      G[a].push_back( b );
      G[b].push_back( a );
    }
    for(int i=0;i<N;i++) bfs(i);
    cout << dijk( 0 ) << endl;
  }
  return 0;
}