#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0596"

#include<bits/stdc++.h>
using namespace std;

#define call_from_test
#ifndef call_from_test
#include<bits/stdc++.h>
using namespace std;
#endif
//BEGIN CUT HERE
template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}
//END CUT HERE
#ifndef call_from_test
signed main(){
  return 0;
}
#endif

#undef call_from_test

vector<int> bfs(int s,vector< vector<int> > G){
  int n=G.size();
  vector<int> dp(n,-1);
  queue<int> que;
  dp[s]=0;
  que.emplace(s);
  while(!que.empty()){
    int v=que.front();que.pop();
    for(int u:G[v]){
      if(~dp[u]) continue;
      dp[u]=dp[v]+1;
      que.emplace(u);
    }
  }
  return dp;
}

signed main(){
  int n,k;
  cin>>n>>k;

  vector<int> cs(n),rs(n);
  for(int i=0;i<n;i++) cin>>cs[i]>>rs[i];

  vector<vector<int> > G(n);
  for(int i=0;i<k;i++){
    int x,y;
    cin>>x>>y;
    x--;y--;
    G[x].emplace_back(y);
    G[y].emplace_back(x);
  }

  vector< vector<int> > di(n);
  for(int i=0;i<n;i++) di[i]=bfs(i,G);

  const int INF = 1e9;
  vector<int> dp(n,INF);
  vector<int> used(n,0);
  dp[0]=0;

  for(int i=0;i<n;i++){
    int u=-1;
    for(int j=0;j<n;j++){
      if(used[j]||dp[j]==INF) continue;
      if(u<0||dp[u]>dp[j]) u=j;
    }
    if(u<0) break;
    used[u]=1;
    for(int j=0;j<n;j++){
      if(di[u][j]>rs[u]) continue;
      chmin(dp[j],dp[u]+cs[u]);
    }
  }

  cout<<dp[n-1]<<endl;
  return 0;
}

