#include <iostream>
#include <queue>
#include <stack>
#include <vector>

using namespace std;

#define loop(i,a,b) for(int i=(a); i<(int)(b); i++)
#define rep(i,b) loop(i,0,b)
#define pb push_back

int n, k;
vector<vector<int>> road, G;
vector<int> c, r;

void make_graph(int s){
    vector<int> d(n, 1 << 30);
    queue<int> q;
    q.push(s);
    d[s] = 0;
    while(q.size()){
        int v = q.front();
        q.pop();
        if(d[v] == r[s]) continue;
        rep(j, road[v].size()){
            int to = road[v][j];
            if(d[to] == 1 << 30){
                q.push(to);
                d[to] = d[v] + 1;
                G[s].pb(to);
            }
        }
    }
}

int dijkstra(int from, int to){
    struct state {
        int v, d;
        bool operator<(const state& s) const{
            return d>s.d;
        }
    };

    vector<int> d(n, 1 << 30);
    vector<bool> vis(n, false);
    priority_queue<state> q;

    d[from] = 0;
    q.push({from, 0});

    while(q.size()){
        state s = q.top(); q.pop();
        if(d[s.v]<s.d) continue;
        vis[s.v] = true;
        rep(i, G[s.v].size()){
            int to = G[s.v][i];
            int cost = c[s.v];
            if(!vis[to] && d[to]>s.d + cost){
                d[to] = s.d + cost;
                q.push({to, d[to]});
            }
        }
    }
    return d[to];
}

int main(){
    cin >> n >> k;
    road.resize(n);
    G.resize(n);
    c.resize(n);
    r.resize(n);
    rep(i, n){
        int a, b; cin >> a >> b;
        c[i] = a; r[i] = b;
    }
    rep(i, k){
        int a, b; cin >> a >> b;
        road[a - 1].pb(b - 1);
        road[b - 1].pb(a - 1);
    }
    rep(i, n) make_graph(i);
    cout << dijkstra(0, n - 1) << endl;
}