#include <cstdio>
#include <queue>
#include <algorithm>
#include <vector>
using namespace std;

typedef pair<int, int> P;
struct Jud{ bool pass; int rest; };
const int MAX_N = 5000;
const int INF = 100000000;
int N, K, C[MAX_N + 1], R[MAX_N + 1], A, B;
int cost[MAX_N + 1];
vector<int> V[MAX_N + 1];
queue<P> que;
Jud jud[MAX_N + 1];

void dfs(int t, int c, int r){
	if(r == 0 || (jud[t].pass && jud[t].rest >= r)) return;
	
	jud[t].pass = true;
	jud[t].rest = r;
	for(int i = 0; i < V[t].size(); i++){
		if(cost[V[t][i]] > c){
			cost[V[t][i]] = c;
			que.push(make_pair(V[t][i], c));
		}
		dfs(V[t][i], c, r - 1);
	}
}

int main(){
	P p;
	int t;
	
	for(int i = 0; i < MAX_N + 1; i++){
		cost[i] = INF;
	}
	
	scanf("%d%d", &N, &K);
	for(int i = 1; i <= N; i++) scanf("%d%d", &C[i], &R[i]);
	for(int i = 1; i <= K; i++){
		scanf("%d%d", &A, &B);
		V[A].push_back(B);
		V[B].push_back(A);
	}
	
	cost[1] = 0;
	que.push(make_pair(1, 0));//(town, cost)
	while(!que.empty()){
		p = que.front();
		que.pop();
		
		t = p.first;
		
		if(p.second != cost[t]) continue;
		
		for(int i = 1; i <= N; i++){
			jud[i].pass = false;
			jud[i].rest = 0;
		}
		dfs(t, cost[t] + C[t], R[t]);
	}
	
	printf("%d\n", cost[N]);
	
	//for(int i = 1; i <= N; i++) printf("cost[%d] = %d\n", i, cost[i].first);
	
	return 0;
}