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

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

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