#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <vector>

#define INF (1 << 28)

using namespace std;

#define MAX_V 12000

struct edge{
	int to;
	int cost;
};

typedef pair<int, int> P; // first??????????????¢???second??????????????????

bool used[MAX_V];
vector<edge> G[MAX_V];
int d[MAX_V];

void shortest_path1(int s, int V){ // V???????????°
	
	priority_queue<P, vector<P>, greater<P> > que;
	
	for(int i = 0; i < V; i++){
		d[i] = INF;
	}
	d[s] = 0;
	
	que.push(P(0, s));
	
	while(!que.empty()){
		
		P p = que.top();
		que.pop();
		
		int v = p.second;
		
		if(d[v] < p.first){
			continue;
		}
		
		for(int i = 0; i < G[v].size(); i++){
			edge e = G[v][i];
			if(d[e.to] > e.cost + d[v]){
				d[e.to] = d[v] + e.cost;
				que.push(P(d[e.to], e.to));
			}
		} // ????????????????°???????????????´??°
	}
}

int cost[5001][5001];

int fare[5001];
int range[5001];

void shortest_path2(int s, int V){
	for(int i = 0; i < V; i++){
		d[i] = INF;
		used[i] = false;
	}
	d[s] = 0;
	while(true){
		
		int add_v = -1;
		
		for(int u = 0; u < V; u++){
			if(!used[u] && (add_v == -1 || d[u] < d[add_v])){
				add_v = u;
			}
		} // ??´??°????????????????±????
		
		if(add_v == -1){
			break;
		} // ??´??°???????????????????????´????????????
		used[add_v] = true;
		
		for(int u = 0; u < V; u++){
			d[u] = min(d[u], d[add_v] + cost[add_v][u]);
		} // ???????????????????????????????°???????????????´??°
	}
}

int main(){
	
	int N, K;
	
	cin >> N >> K;
	
	for(int i = 0; i < N; i++){
		cin >> fare[i] >> range[i];
	}
	
	for(int i = 0; i < K; i++){
		int num1, num2;
		cin >> num1 >> num2;
		num1--;
		num2--;
		
		edge e1, e2;
		e1.to = num2;
		e2.to = num1;
		e1.cost = 1;
		e2.cost = 1;
		G[num1].push_back(e1);
		G[num2].push_back(e2);
	}
	
	for(int i = 0; i < N; i++){
		shortest_path1(i, N);
		for(int j = 0; j < N; j++){
			if(d[j] <= range[i]){
				cost[i][j] = fare[i];
			}else{
				cost[i][j] = INF;
			}
			//cout << cost[i][j] << " ";
		}
		//cout << endl;
	}
	
	shortest_path2(0, N);
	
	cout << d[N - 1] << endl;
	
	
	return 0;
}