#include<stdio.h>
#include<queue>
#include<vector>
#include<algorithm>
using namespace std;
vector<int> g[11000];
vector<int> g2[11000];
int c[11000];
int r[11000];
int ijk[11000];
int v[11000];
int bfs[11000];
int main(){
	int a,b;
	scanf("%d%d",&a,&b);
	for(int i=0;i<a;i++){
		scanf("%d%d",c+i,r+i);
	}
	for(int i=0;i<b;i++){
		int p,q;scanf("%d%d",&p,&q);p--;q--;
		g[p].push_back(q);g[q].push_back(p);
	}
	for(int i=0;i<a;i++){
		for(int j=0;j<a;j++)bfs[j]=-1;
		bfs[i]=0;
		queue<int>Q;
		Q.push(i);
		while(Q.size()){
			int at=Q.front();Q.pop();
			for(int j=0;j<g[at].size();j++){
				if(!~bfs[g[at][j]]){
					bfs[g[at][j]]=bfs[at]+1;
					Q.push(g[at][j]);
				}
			}
		}
		for(int j=0;j<a;j++){
			if(~bfs[j]&&bfs[j]<=r[i]){
				g2[i].push_back(j);
			}
		}
	}
	priority_queue<pair<int,int> >Q;
	for(int i=0;i<a;i++){
		ijk[i]=999999999;
		v[i]=0;
	}
	ijk[0]=0;
	Q.push(make_pair(0,0));
	while(Q.size()){
		int cost=-Q.top().first;
		int at=Q.top().second;Q.pop();
		if(v[at])continue;v[at]=1;
		for(int i=0;i<g2[at].size();i++){
			if(!v[g2[at][i]]&&ijk[g2[at][i]]>cost+c[at]){
				ijk[g2[at][i]]=cost+c[at];
				Q.push(make_pair(-ijk[g2[at][i]],g2[at][i]));
			}
		}
	}
	printf("%d\n",ijk[a-1]);
}