#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef pair<int,int> P;

class dijkstra{
  public:
	struct edge{ int to, cost;};
	int V;
	vector<vector<edge> > G;
	vector<int> d;
	dijkstra(int nv){ // nv:ノード数
		nv += 10;
		d = vector<int>(nv); 
		V = nv;
		G = vector<vector<edge> >(nv);
	}
		
	void run(int s){
		priority_queue<P, vector<P>, greater<P> > que;
		fill(d.begin(), d.end(), INT_MAX); // 型をlong longにした時はLLONG_MAXにすること。
		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] > d[v] + e.cost){
					d[e.to] = d[v] + e.cost;
					que.push(P(d[e.to],e.to));
				}
			}
		}
	}
};

int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);

	int n,k; cin >> n >> k;
	int c[5005],r[5005];
	dijkstra D(n);

	for (int i = 0;i < n;i++){
		cin >> c[i] >> r[i];
	}

	vector<int> way[5005];

	for (int i = 0;i < k;i++){
		int a,b; cin >> a >> b;
		a--; b--;
		way[a].push_back(b);
		way[b].push_back(a);
	}

	for (int i = 0;i < n;i++){
		queue<int> que;
		que.push(i);
		int d[5005]; memset(d,-1,sizeof(d));
		d[i] = 0;
		while(que.size()){
			int now = que.front(); que.pop();
			if(d[now] == r[i]) break;
			for (int j = 0;j < way[now].size();j++){
				int to = way[now][j];
				if(d[to] != -1) continue;
				que.push(to);
				d[to] = d[now]+1;
				D.G[i].push_back({to,c[i]});
			}
		}
	}

	D.run(0);
	cout << D.d[n-1] << endl;

	return 0;

}

