#include <iostream>
#include <set>
#include <stack>
#include <queue>
#include <utility>
#include <algorithm>
#define INF 1000000000
using namespace std;

int ned[5010],dis[5010],ans[5010];
set<int> ary[5010];
bool kaku[5010]={};

//????¢??????????????????¨???????????????
void ssm(int a,set<int> &s){
	stack<int> st,st2,*sti,*sto;
	set<int>::iterator it;
	set<int> ss;
	int tmp,l;
	l=dis[a];
	s.clear();
	st2.push(a);
	//cout<<"in ssm "<<a<<" "<<l<<endl;//
	for(int cnt=0;cnt<l;cnt++){
		if(cnt%2){
			sti=&st;
			sto=&st2;
		}
		else{
			sti=&st2;
			sto=&st;
		}
		while(!(*sto).empty())(*sto).pop();
		while(!(*sti).empty()){
			tmp=(*sti).top();
			(*sti).pop();
			it=ary[tmp].begin();
			while(it!=ary[tmp].end()){
				if(ss.find(*it)==ss.end()){
					(*sto).push(*it);
					ss.insert(*it);
					if(!kaku[*it])  s.insert(*it);
				}
				it++;
			}
		}
		/*//
		cout<<" "<<cnt<<":";
		it=s.begin();
		while(it!=s.end()){
			cout<<*it<<" ";
			it++;
		}
		cout<<endl;
		
		*///
	}
}

int main(){
	int N,K,hog,bak;
	pair<int,int> tm;
	set<int>::iterator it;
	set<int> tmp;
	priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > pq;//first?????¢second???
	cin>>N>>K;
	fill(ans,ans+N+1,INF);
	for(int i=1;i<=N;i++){
		cin>>ned[i]>>dis[i];
	}
	for(int i=0;i<K;i++){
		cin>>hog>>bak;
		ary[hog].insert(bak);
		ary[bak].insert(hog);
	}
	ans[1]=0;
	kaku[1]=true;
	pq.push(make_pair(ned[1],1));
	while(!pq.empty()){
		tm=pq.top();
		pq.pop();
		//cout<<tm.second<<"??????"<<endl;//
		ssm(tm.second,tmp);
		for(it=tmp.begin();it!=tmp.end();it++){
			ans[*it]=tm.first;
			pq.push(make_pair(ans[*it]+ned[*it],*it));
			kaku[*it]=true;
			//cout<<*it<<"?¢???? ?????¢???"<<ans[*it]<<" ";//
		}
		//cout<<endl;//
		
	}
	cout<<ans[N]<<endl;
	return 0;
}