#include <iostream>
#include <queue>
#include <vector>
#define INF 1e+9
using namespace std;

typedef pair<int,int> P;
struct edge{ int to,cost; };

int main(){
	int n,k,c[5000],r[5000];
	int d[5000];
	vector<int> vec[5000];
	vector<edge> G[5000];
	cin >> n >> k;
	for(int i = 0;i < n;i++){
		cin >> c[i] >> r[i];
		d[i] = INF;
	}
	d[0] = 0;
	for(int i = 0;i < k;i++){
		int a,b;
		cin >> a >> b; a--;b--;
		vec[a].push_back(b);
		vec[b].push_back(a);
	}
	for(int i = 0;i < n;i++){
		bool used[5000] = {};
		queue<int> que;
		que.push(i);
		used[i] = true;
		for(int j = 0;j < r[i];j++){
			int siz = que.size();
			for(int k = 0;k < siz;k++){
				int v = que.front();que.pop();
				for(int l = 0;l < vec[v].size();l++){
					if(!used[vec[v][l]]){
						G[i].push_back({vec[v][l],c[i]});
						used[vec[v][l]] = true;
						que.push(vec[v][l]);
					}
				}
			}
		}
	}
	priority_queue<P,vector<P>,greater<P> > que;
	que.push(P(0,0));
	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[v] + e.cost < d[e.to]){
				d[e.to] = d[v] + e.cost;
				que.push(P(d[e.to],e.to));
			}
		}
	}
	cout << d[n - 1] << endl;
	return 0;
}