#include <cstdio>
#include <algorithm>
#include <queue>
#include <climits>
#include <vector>
#include <cstring>

using namespace std;

vector<int> G[5000];
priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > pq;

int N;
int cost[5000], rep[5000], tot[5000], vis[5000];
bool done[5000], looked[5000];

void visit(int v, int left, int needed)
{
	tot[v] = min(tot[v], needed);
	if (!done[v]) pq.push(make_pair(tot[v], -v));
	
	if (!left) return;
	for (int i = 0; i < G[v].size(); i++)
		vis[G[v][i]] = max(vis[G[v][i]], left - 1);
	
	for (int i = 0; i < G[v].size(); i++)
		if (vis[G[v][i]] == left - 1)
			visit(G[v][i], left - 1, needed);
}

int main()
{
	int M;
	
	scanf("%d %d", &N, &M);
	
	for (int i = 0; i < N; i++){
		scanf("%d %d", cost + i, rep + i);
	}
	
	for (int i = 0; i < M; i++){
		int x, y;
		scanf("%d %d", &x, &y);
		G[--x].push_back(--y);
		G[y].push_back(x);
	}
	
	for (int i = 0; i < N; i++) tot[i] = INT_MAX;
	
	tot[0] = 0;
	pq.push(make_pair(0, 0));
	while (pq.size()){
		pair<int, int> x = pq.top(); pq.pop();
		if (done[-x.second]) continue;
		done[-x.second] = true;
		memset(vis, -1, sizeof(vis));
		memset(looked, 0, sizeof(looked));
		if (-x.second == N - 1) return (!printf("%d\n", x.first));
		vis[-x.second] = rep[-x.second];
		visit(-x.second, rep[-x.second], x.first + cost[-x.second]);
	}
	return (0);
}