#include <bits/stdc++.h>
#define ll long long
#define INF 1000000005
#define MOD 1000000007
#define rep(i,n) for(int i=0;i<n;++i)

using namespace std;

typedef pair<int,int>P;

struct edge{
	int to;
	int cost;
};

const int MAX_N = 5001;

int n,k;
ll d[MAX_N];
int c[MAX_N];
int r[MAX_N];
int dd[MAX_N][MAX_N];
deque<int> deq;
vector<int> G[MAX_N];
vector<edge> GG[MAX_N];

void dijkstra(int s)
{
	priority_queue<P,vector<P>,greater<P> > que;
	d[s] = 0;
	que.push(P(0,s));
	while(!que.empty()){
		P p = que.top();
		que.pop();
		int v = p.second;
		if(d[v] < p.first) continue;
		vector<edge>::iterator it = GG[v].begin();
		while(it != GG[v].end()){
			if(d[it->to] > d[v] + it->cost){
				d[it->to] = d[v] + it->cost;
				que.push(P(d[it->to],it->to));
			}
			it++;
		}
	}
}

int main()
{
	int x,y;
	scanf("%d%d",&n,&k);
	rep(i,n){
		scanf("%d%d",&c[i],&r[i]);
	}
	rep(i,k){
		scanf("%d%d",&x,&y);
		G[x-1].push_back(y-1);
		G[y-1].push_back(x-1);
	}
	rep(i,n){
		fill(dd[i],dd[i]+n,INF);
		deq.push_back(i);
		dd[i][i]=0;
		while(!deq.empty()){
			int u = deq[0];
			deq.pop_front();
			rep(j,G[u].size()){
				if(dd[i][G[u][j]]>dd[i][u]+1){
					dd[i][G[u][j]]=dd[i][u]+1;
					deq.push_back(G[u][j]);
				}
			}
		}
	}
	rep(i,n){
		rep(j,n){
			if(dd[i][j]<=r[i]){
				edge e;
				e.to = j,e.cost=c[i];
				GG[i].push_back(e);
			}
		}
	}
	fill(d,d+n,(1LL << 60));
	dijkstra(0);
	printf("%lld\n",d[n-1]);
	return 0;
}