// AOJ 0596 (http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0596)
#include<cstdio>
#include<algorithm>
#include<limits>
#include<vector>
#include<queue>
#define rep(i,a) for(int i=0;i<(a);++i)

const int MAX_N = 5000, INF = std::numeric_limits<int>::max()>>2;

struct St
{
	int v, cost, rest;

	St( int v, int cost, int rest )
	:	v(v), cost(cost), rest(rest)
	{}

	bool operator< ( const St &s ) const
	{ return cost > s.cost; }
};

int N, K;
int C[MAX_N], R[MAX_N];
std::vector<int> G[MAX_N];

int dp[MAX_N][MAX_N+1];

int main()
{
	scanf( "%d%d", &N, &K );
	rep( i, N )
		scanf( "%d%d", C+i, R+i );

	rep( i, K )
	{
		int A, B;
		scanf( "%d%d", &A, &B );
		--A; --B;
		G[A].push_back(B);
		G[B].push_back(A);
	}

	std::priority_queue<St> pque;
	pque.push( St( 0, C[0], R[0] ) );
	rep( i, N ) rep( j, N+1 )
		dp[i][j] = INF;
	dp[0][R[0]] = C[0];

	while( !pque.empty() )
	{
		St s = pque.top(); pque.pop();
		int v = s.v, c = s.cost, r = s.rest;

		if( v == N-1 )
			break;

		if( dp[v][r] < c )
			continue;

		if( r ) rep( i, G[v].size() )
		{
			int u = G[v][i];

			if( dp[u][r-1] > c )
			{
				dp[u][r-1] = c;
				pque.push( St( u, dp[u][r-1], r-1 ) );
			}
		}

		if( dp[v][R[v]] > dp[v][r]+C[v] )
		{
			dp[v][R[v]] = dp[v][r]+C[v];
			pque.push( St( v, dp[v][R[v]], R[v] ) );
		}
	}

	printf( "%d\n", *std::min_element( dp[N-1], dp[N-1]+N ) );

	return 0;
}