#include <bits/stdc++.h>
#define int long long
#define double long double
#define rep(i, a, n) for(int i = (int)(a);(i) < (int)(n);++(i))
#define repe(i, a, n) for(int i = (int)(a);(i) <= (int)(n);++(i))
#define repif(i, a, x) for(int i = (int)(a);(x);++(i))
#define repr(i, a, n) for(int i = ((int)(a)-1);(i) >= (int)(n);--(i))
#define reper(i, a, n) for(int i = (int)(a);(i) >= (int)(n);--(i))
#define SZ(x) ((int)(x).size())
#define ALL(x) begin(x), end(x)
#define CEIL(x) ((int)ceil(((double)x)))
#define POW(x, y) ((int)pow(x, y))
#define UNIQUE(x) (x).erase(unique(ALL((x))), end(x))
#define gcd(x, y) __gcd(x, y)
#define lcm(x, y) ((x)/gcd(x,y)*(y))
#define isin(x, l, r) ((l) <= (x) and (x) < (r))
#define fcout(n) cout << fixed << setprecision(n)
#define rcout(n) cout << right << setw(n)
#define pb push_back
#define eb emplace_back
#define lb lower_bound
#define ub upper_bound
#define PI (acosl(-1))
#define EPS (1e-10)
#define INF LLONG_MAX
#define INF32 INT32_MAX
#define MOD 1000000007LL
using namespace std;
using VI = vector<int>;
using VVI = vector<vector<int>>;
using PII = pair<int, int>;
using TIII = tuple<int, int, int>;
using VPII = vector<pair<int, int>>;
using VTIII = vector<tuple<int, int, int>>;
using Complex = complex<double>;
template<typename T, template<typename> typename C = less> using PQ = priority_queue<T, vector<T>, C<T>>;
template<typename T> inline bool chmax(T& a, const T& b, bool t = false){ if(a<b or (t and a==b)){ a=b; return true; } return false; }
template<typename T> inline bool chmin(T& a, const T& b, bool t = false){ if(a>b or (t and a==b)){ a=b; return true; } return false; }


template<typename T>
struct Dijkstra {
    struct Edge {
        int to;
        T cost;
        Edge(int to, T cost) : to(to), cost(cost){}
        bool operator<(const Edge& e) const { return cost > e.cost; }
    };
    vector<vector<Edge>> G;
    vector<T> ds;
    vector<int> bs;
    Dijkstra() = default;
    Dijkstra(int n) : G(n){}
    void addEdge(int u, int v, T c){
        G[u].emplace_back(v, c);
    }
    void build(int s){
        int n = G.size();
        ds.assign(n, numeric_limits<T>::max());
        bs.assign(n, -1);
        priority_queue<Edge> pq;
        ds[s] = 0;
        pq.emplace(s, ds[s]);
        while(!pq.empty()){
            auto p = pq.top(); pq.pop();
            int v = p.to;
            if(ds[v] < p.cost) continue;
            for(auto e : G[v]){
                if(ds[e.to] > ds[v]+e.cost){
                    ds[e.to] = ds[v]+e.cost;
                    bs[e.to] = v;
                    pq.emplace(e.to, ds[e.to]);
                }
            }
        }
    }
    T operator[](int k){ return ds[k]; }
    vector<int> restore(int to){
        vector<int> res;
        if(bs[to] < 0) return res;
        while(~to) res.emplace_back(to), to = bs[to];
        reverse(begin(res), end(res));
        return res;
    }
};


int N, K;
int C[5010], R[5010];
VI g[5010];


signed main(){
    cin >> N >> K;
    rep(i, 0, N) cin >> C[i] >> R[i];
    rep(i, 0, K){
        int a, b;
        cin >> a >> b;
        a--;
        b--;
        g[a].pb(b);
        g[b].pb(a);
    }

    Dijkstra<int> G(N);
    rep(i, 0, N){
        queue<int> q;
        VI d(N);
        q.push(i);
        while(!q.empty()){
            int v = q.front(); q.pop();
            for(int u : g[v]) if(d[u] == 0) d[u] = d[v]+1, q.push(u);
        }
        rep(j, 0, N) if(i != j and d[j] <= R[i]) G.addEdge(i, j, C[i]);
    }

    G.build(0);

    cout << G[N-1] << endl;

    return 0;
}


Measured memory_bytes: 237300