#include<iostream>
#include<queue>
#include<vector>
#include<map>
#include<cstring>
using namespace std;
bool used[5005];
int town[5005][2];//??????????????¢
vector<int> v1[5005];
vector<pair<int,int> > v2[5005];
queue<int> bfs;
priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > q1;

int main(){
	int n,m;
	int i,j,k,l;
	int a,b,c;
	cin>>n>>m;
	for(i=0;i<n;i++){
		cin>>town[i][0]>>town[i][1];
	}
	for(i=0;i<m;i++){
		cin>>a>>b;
		a--,b--;
		v1[a].push_back(b);
		v1[b].push_back(a);
	}
	for(i=0;i<n;i++){
		for(j=0;j<v1[i].size();j++){
			bfs.push(v1[i][j]);
		}
		used[i]=true;
		for(j=0;j<town[i][1];j++){
			c=bfs.size();
			for(k=0;k<c;k++){//
				a=bfs.front(),bfs.pop();
				if(used[a])continue;
				used[a]=true;
				v2[i].push_back(make_pair(a,town[i][0]));
				for(l=0;l<v1[a].size();l++){
					if(used[v1[a][l]])continue;
					bfs.push(v1[a][l]);
				}
			}
		}
		memset(used,false,sizeof(used));
		while(!bfs.empty()){bfs.pop();}
	}
	q1.push(make_pair(0,0));
	while(!q1.empty()){
		a=q1.top().first,b=q1.top().second,q1.pop();
		if(b==n-1)break;
		if(used[b])continue;
		used[b]=true;
		for(i=0;i<v2[b].size();i++){
			if(used[v2[b][i].first])continue;
			q1.push(make_pair(v2[b][i].second+a,v2[b][i].first));
		}
	}
	cout<<a<<endl;
	return 0;
}