#include<bits/stdc++.h>
#define PB push_back
#define MP make_pair
using namespace std;
typedef long long int LL;
typedef pair<int, int> PII;
typedef vector<PII> VP;
typedef VP::iterator VPI;
typedef string::iterator STI;

int n, k;
int c[5010], r[5010];

vector<int> df_cango[5010];
bool df_visited[5010];

vector<int> dj_cango[5010];
bool dj_visited[5010];
priority_queue<PII, VP, greater<PII> > dj_search;

void dfs(int start)
{
  queue<int> df_search;
  memset(df_visited, false, sizeof df_visited);

  df_search.push(start);
  df_visited[start] = true;
  
  for(int i = 1; i <= r[start]; i++){
    int sz = df_search.size();
    for(int j = 0; j < sz && !df_search.empty(); j++){
      int now = df_search.front();
      df_search.pop();

      for(int k = 0; k < df_cango[now].size(); k++){
	if(!df_visited[df_cango[now][k]]){
	  df_visited[df_cango[now][k]] = true;
	  dj_cango[start].PB(df_cango[now][k]);
	  df_search.push(df_cango[now][k]);
	}
      }
    }
  }

  return;
}

int dijk()
{
  dj_search.push(MP(0, 1));
  
  while(!dj_search.empty()){
    PII now = dj_search.top();
    dj_search.pop();

    if(now.second == n)
      return now.first;

    if(!dj_visited[now.second]){
      dj_visited[now.second] = true;
      for(int i = 0; i < dj_cango[now.second].size(); i++){
	if(!dj_visited[dj_cango[now.second][i]]){
	  dj_search.push(MP(now.first + c[now.second], dj_cango[now.second][i]));
	}
      }
    }
  }			 
}

int main()
{
  cin >> n >> k;
  for(int i = 1; i <= n; i++)
    cin >> c[i] >> r[i];
  for(int i = 1; i <= k; i++){
    int a, b;
    cin >> a >> b;
    df_cango[a].PB(b);
    df_cango[b].PB(a);
  }

  for(int i = 1; i <= n; i++)
    dfs(i);

  cout << dijk() << endl;
  
  return 0;
}