#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <map>
#include <sstream>
#include <queue>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <iterator>
#include <stack>
#include <list>
using namespace std;
typedef long long int lli;
typedef pair<int,int> P;
#define F first
#define S second
const int INF=1000000000;

const int MAX_V=5001;
int cost[MAX_V][MAX_V];
int cnt[MAX_V][MAX_V];
vector<int> e[MAX_V];
P t[MAX_V];
int n,k;
bool used[MAX_V];
int d[MAX_V];

void hoge(int s,int now,int C,int R,bool f[],int cnt){
	if(R==cnt) return;
	for(int i=1; i<=n; ++i){
		if(!f[i]&&e[now][i]){
			f[i]=true;
			cost[s][i]=C;
			hoge(s,i,C,R,f,cnt+1);
			f[i]=false;
		}
	}
}

int main(){
	cin >> n >> k;
	clock_t t1,t2,t3,t4;
	memset(e,0,sizeof(e));
	for(int i=1; i<=n; ++i){
		int c,r;
		cin >> c >> r;
		t[i].F=c;
		t[i].S=r;
	}
	for(int i=1; i<=k; ++i){
		int a,b;
		cin >> a >> b;
		//e[a][b]=e[b][a]=true;
		e[a].push_back(b);
		e[b].push_back(a);
	}
	
	for(int i=1; i<=n; ++i){
		for(int j=1; j<=n; ++j){
			cost[i][j]=INF;
			cnt[i][j]=INF;
			if(i==j) cost[i][j]=0;
		}
	}
	
	for(int i=1; i<=n; ++i){
		bool f[MAX_V];
		memset(f,0,sizeof(f));
		f[i]=true;
		queue<int> que;
		que.push(i);
		cnt[i][i]=0;
		while(que.size()){
			int now=que.front();
			que.pop();
			for(int j=0; j<e[now].size(); ++j){
				if(!f[e[now][j]]&&cnt[i][now]+1<=t[i].S){
					que.push(e[now][j]);
					cnt[i][e[now][j]]=cnt[i][now]+1;
					f[e[now][j]]=true;
				}
			}
		}
	}
	
	for(int i=1; i<=n; ++i){
		for(int j=1; j<=n; ++j){
			if(cnt[i][j]!=INF&&i!=j) cost[i][j]=t[i].F;
			//cout << cost[i][j] << " ";
		}
		//cout << "\n";
	}
	
	memset(used,0,sizeof(used));
	fill(d,d+n+1,INF);
	d[1]=0;
	while(true){
		int v=-1;
		for(int u=1; u<=n; ++u){
			if(!used[u]&&(v==-1||d[v]>d[u])) v=u;
		}
		if(v==-1) break;
		used[v]=true;
		for(int u=1; u<=n; ++u){
			d[u]=min(d[u],d[v]+cost[v][u]);
		}
	}
	cout << d[n] << "\n";
	
	return 0;
}