#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <functional>
#include <string.h>

using namespace std;
typedef pair<int, int> P;
static const int INF = 2e9;

struct Edge
{
	int to;
	int cost;
};
vector<Edge> G1[5001];
vector<Edge> G2[5001];
int d[5001];
bool isUsed[5001];

void solve()
{
	int N, K;
	cin >> N >> K;
	vector<int> C(N);
	vector<int> R(N);
	for (int i = 0; i < N; ++i)
	{
		cin >> C[i] >> R[i];
	}
	for (int i = 0; i < K; ++i)
	{
		int from, to;
		Edge e1, e2;
		cin >> from >> to;
		--from; --to;
		e1.to = to;
		e1.cost = 1;
		e2.to = from;
		e2.cost = 1;
		G1[from].push_back(e1);
		G1[to].push_back(e2);
	}
	for (int i = 0; i < N; ++i)
	{
		memset(isUsed, 0, sizeof(isUsed));
		queue<P> que;
		que.push(P(i, R[i]));
		isUsed[i] = true;
		while (!que.empty())
		{
			P p = que.front();
			que.pop();
			int v = p.first;
			for (int j = 0; j < G1[v].size(); ++j)
			{
				int to = G1[v][j].to;
				if (!isUsed[to] && p.second >= 1)
				{
					isUsed[to] = true;
					que.push(P(to, p.second - 1));
					Edge e;
					e.to = to;
					e.cost = C[i];
					G2[i].push_back(e);
				}
			}
		}
	}

	for (int i = 0; i < N; ++i)
	{
		d[i] = INF;
	}
	priority_queue<P, vector<P>, greater<P> > pque;
	pque.push(P(0, 0));
	d[0] = 0;
	while (!pque.empty())
	{
		P p = pque.top();
		pque.pop();
		int v = p.first;
		for (int i = 0; i < G2[v].size(); ++i)
		{
			Edge e = G2[v][i];
			if (d[e.to] > p.second + e.cost)
			{
				d[e.to] = p.second + e.cost;
				pque.push(P(e.to, d[e.to]));
			}
		}
	}
	cout << d[N - 1] << endl;
}

int main()
{
	solve();
	return(0);
}