#include<bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
using namespace std;
typedef vector<int> vi;
typedef pair<int,int> pii;

int main(){
  cin.tie(0); ios::sync_with_stdio(0);
  int n,k;
  cin >> n >> k;
  vi c(n),r(n);
  rep(i,n)cin >> c[i] >> r[i];

  vector<vi> g(n);
  rep(i,k){
    int a,b;
    cin >> a >> b; a--; b--;
    g[a].push_back(b);
    g[b].push_back(a);
  }

  vi dis(n,1e9), use(n,0);
  dis[0] = 0;
  for(;;){
    int v = -1;
    rep(i,n){
      if(!use[i] && (v<0 || dis[v] > dis[i]))v = i;
    }
    if(v<0 || v==n-1)break;
    use[v] = 1;

    vi d(n,-1); d[v] = 0;
    queue<int> q; q.push(v);

    while(q.size()){
      int cur = q.front(); q.pop();
      if(d[cur]==r[v])break;

      for(int nxt : g[cur]){
	if(d[nxt] < 0){
	  dis[nxt] = min(dis[nxt], dis[v] + c[v]);
	  d[nxt] = d[cur] + 1;
	  q.push(nxt);
	}
      }
    }
  }
  cout << dis[n-1] << endl;
}