#include "iostream"
#include "climits"
#include "list"
#include "queue"
#include "stack"
#include "set"
#include "functional"
#include "algorithm"
#include "math.h"
#include "utility"
#include "string"
#include "map"
#include "unordered_map"
#include "iomanip"
#include "random"

using namespace std;
const long long int MOD = 1000000007;

int N, K;
list<int>edge[5000];
list<int>can;
queue<int>box;
priority_queue<long long int, vector<long long int>, greater<long long int>>Q;

int main() {
	ios::sync_with_stdio(false);
	cin >> N >> K;
	vector<int>cost(N);
	vector<int>far(N);
	vector<int>dis(N, INT_MAX);
	dis[0] = 0;
	for (int i = 0; i < N; i++)cin >> cost[i] >> far[i];
	for (int i = 0; i < K; i++) {
		int a, b;
		cin >> a >> b;
		a--;
		b--;
		edge[a].push_back(b);
		edge[b].push_back(a);
	}
	vector<int>move(N, INT_MAX);
	Q.push(0);
	while (!Q.empty()) {
		int current = Q.top() % MOD;
		int dist = Q.top() / MOD;
		box.push(current);
		for (int i = 0; i < N; i++)move[i] = INT_MAX;
		move[current] = 0;
		while (!box.empty()) {
			for (auto j : edge[box.front()]) {
				if (move[j] > move[box.front()] + 1) {
					move[j] = move[box.front()] + 1;
					box.push(j);
				}
			}
			box.pop();
		}
		for (int j = 0; j < N; j++) {
			if (move[j] && move[j] <= far[current])can.push_back(j);
		}
		for (auto i : can) {
			if (dis[i] > dist + cost[current]) {
				dis[i] = dist + cost[current];
				Q.push(dis[i] * MOD + i);
			}
		}
		can.clear();
		Q.pop();
	}
	cout << dis[N - 1] << endl;
	return 0;
}