#include <bits/stdc++.h>
#include<stdio.h>
using namespace std;
#define FOR(i,k,n) for(int i = (k); i < (n); i++)
#define REP(i,n) FOR(i,0,n)
#define ALL(a) begin(a),end(a)
#define MS(m,v) memset(m,v,sizeof(m))
#define D10  fixed<<setprecision(10)
typedef vector<int> vi;
typedef vector<string> vs;
typedef pair<int, int> P;
typedef long long ll;
const ll INF = 114514810;
const ll MOD = 1000000007;
const double EPS = 1e-8;
const double PI = acos(-1.0);
struct edge
{
	short to, cost;
	bool operator < (const edge& e) const { return cost < e.cost; }
	bool operator >(const edge& e) const { return cost > e.cost; }
};
int dx[] = { -1, 0, 0, 1 }; int dy[] = { 0, -1, 1, 0 };
bool valid(int x, int y, int h, int w) { return (x >= 0 && y >= 0 && x < h&&y < w); }
///*************************************************************************************///
///*************************************************************************************///
///*************************************************************************************///


int d[5005];
vector<vector<edge>> es;

void dijkstra(int s)
{
	fill(ALL(d), INF);
	d[s] = 0;
	priority_queue<P, vector<P>, greater<P>> que;
	que.push(P(0, s));
	while (!que.empty())
	{
		P p = que.top(); que.pop();
		int v = p.second;
		if (d[v] < p.first) continue;
		REP(i, es[v].size())
		{
			edge e = es[v][i];
			if (d[e.to] > d[v] + e.cost)
			{
				d[e.to] = d[v] + e.cost;
				que.push(P(d[e.to], e.to));
			}
		}
	}
}

int main()
{
	int n, k;
	bool memo[5000];
	cin >> n >> k;
	es.clear();
	es.resize(n);
	short c[5000], r[5000];
	REP(i, n) cin >> c[i] >> r[i];
	vector<vi> v(n);
	REP(i, k)
	{
		int a, b;
		cin >> a >> b;
		a--; b--;
		v[a].push_back(b);
		v[b].push_back(a);
	}
	vector<short> res;
	queue<P> que;
	REP(i, n)
	{
		MS(memo, 0);
		res.clear();
		while (que.size()) que.pop();
		que.push(P(i, 0));
		while (que.size())
		{
			int tmp = que.front().first;
			int dis = que.front().second;
			memo[tmp] = true;
			que.pop();
			if (dis > r[i]) break;
			res.push_back(tmp);
			REP(j, v[tmp].size())
			{
				if (!memo[v[tmp][j]])
				{
					que.push(P(v[tmp][j], dis + 1));
				}
			}
		}
		REP(j, res.size()) es[i].push_back(edge{ res[j], c[i] });
	}
	dijkstra(0);
	cout << d[n - 1] << endl;
	return 0;
}