#include <bits/stdc++.h>
#define N 5001
#define INF 1e9
using namespace std;
int n,m;
int G[N][N];
int C[N],R[N];
vector<int> g[N];
typedef pair<int,int> P;

vector<int> bfs(int start){
  vector<int>res,D(N,R[start]+1);
  queue<int> Q;
  Q.push(start);
  D[start]=0;
  while(!Q.empty()){
    int pos = Q.front();Q.pop();
    for(int i=0;i<g[pos].size();i++) {
      int nx=g[pos][i];
      if(D[nx]>D[pos]+1){
	Q.push(nx),D[nx]=D[pos]+1;
	res.push_back(nx);
      }
    }
  }
  return res;
}

int dijkstra(){
  vector<int>D(N,INF); 
  priority_queue<P,vector<P>,greater<P> > Q;
  Q.push(P(0,0));
  D[0] = 0;
  while(!Q.empty()){
    P t=Q.top();Q.pop();
    int pos=t.second;
    int cost=t.first;
    if(pos==n-1) return cost;
    vector<int> nx=bfs(pos);

    for(int i=0;i<nx.size();i++){
      int npos=nx[i];
      int ncost=cost+C[pos];
      if(D[npos]>ncost){
	Q.push(P(ncost,npos));
	D[npos] = ncost;
      }
    }
  }
  return -1;
}


int main(){
  cin>>n>>m;
  for(int i=0;i<n;i++)cin>>C[i]>>R[i];
  
  for(int i=0,a,b;i<m;i++){
    cin>>a>>b;
    a--,b--;
    g[a].push_back(b);
    g[b].push_back(a);
  }
  
  cout<<dijkstra()<<endl;
  return 0;
}