#include<iostream>
#include<queue>
#include<vector>

#define INF 100000000
#define Max_N 5001

typedef std::pair<int,int> pair;

int n,k;
std::vector<std::vector<int> >data_a;
pair data_b[Max_N];
int dijkstra[Max_N][Max_N];
int cost[Max_N];
bool used[Max_N];

void bfs(int i){
	int distance[Max_N];
	for(int j=0;j<=n;j++)distance[j]=0,dijkstra[i][j]=INF;
	distance[i]=0;
	std::queue<int>que;
	que.push(i);
	while(que.size()){
		int j=que.front();que.pop();
		for(unsigned int k=0;k<data_a[j].size();k++){
			int a=data_a[j][k];
			if(distance[a]==0){
				distance[a]=distance[j]+1;
				que.push(a);
			}
		}
	}
	for(int j=1;j<=n;j++){
		if(i!=j&&distance[j]<=data_b[i].second)dijkstra[i][j]=data_b[i].first;
	}
}

void solve(int s){
	cost[s]=0;
	while(true){
		int v=-1;
		for(int i=1;i<=n;i++){
			if(!used[i]&&(v==-1||cost[i]<cost[v]))v=i;
		}
		if(v==-1)break;
		used[v]=true;
		for(int i=1;i<=n;i++){
			cost[i]=std::min(cost[i],cost[v]+dijkstra[v][i]);
		}
	}
}

int main(){
	std::cin>>n>>k;
	for(int i=0;i<=n;i++){
		data_a.push_back(std::vector<int>());
		cost[i]=INF;
		used[i]=false;
	}
	for(int i=1;i<=n;i++){
		int a,b;
		std::cin>>a>>b;
		data_b[i]=pair(a,b);
	}
	for(int i=0;i<k;i++){
		int a,b;
		std::cin>>a>>b;
		data_a[a].push_back(b);
		data_a[b].push_back(a);
	}
	for(int i=1;i<=n;i++)bfs(i);
	solve(1);
	std::cout<<cost[n]<<std::endl;
	return 0;
}