import std.stdio;
import std.c.stdio;
import std.range;
import std.array;
import std.functional;
import std.algorithm;
import std.conv;
import std.container;
import std.math;
import std.numeric;
import std.string;
import std.c.string;
import std.regex;
import std.typecons;
 
void main() {
    int N, K; readf("%d %d\n", &N, &K);
    auto C = new int[N],
         R = new int[N];
    foreach (i; 0 .. N) {
        readf("%d %d\n", &C[i], &R[i]);
    }
    //R.writeln;
    //C.writeln;
    auto g = new int[][N];
    foreach (i; 0 .. K) {
        int A, B; 
        readf("%d %d\n", &A, &B);
        A--; B--;
        g[A] ~= B;
        g[B] ~= A;
    }

    auto G = new int[][N];
    foreach (i; 0 .. N) {
        struct S { int x, k; }
        DList!S Q; Q.insert(S(i, R[i]));
        auto used = new bool[N];
        used[i] = true;
        foreach (j; g[i]) {
            if (used[j]) continue;
            used[j] = true;
            G[i] ~= j;
            Q.insert(S(j, R[i] - 1));
        }
        while (!Q.empty) {
            S n = Q.front; Q.removeFront;
            if (n.k == 0) continue;
            foreach (j; g[n.x]) {
                if (used[j]) continue;
                G[i] ~= j;
                used[j] = true;
                Q.insert(S(j, n.k - 1));
            }
        }
    }

    struct T { int v, w; }
    BinaryHeap!(Array!T, "a.w > b.w") PQ; PQ.insert(T(0, 0));
    auto d = new int[N];
    d[] = int.max; d[0] = 0;
    auto used = new bool[N];
    used[0] = true;
    while (!PQ.empty) {
        T n = PQ.front; PQ.removeFront;
        foreach (v; G[n.v]) {
            if (used[v]) continue;
            int nw = n.w + C[n.v];
            if (nw < d[v]) {
                d[v] = nw;
                PQ.insert(T(v, nw));
            }
        }
    }

    d[N - 1].writeln;

    /*
    foreach (i; 0 .. N) {
        writeln(i + 1, " ", G[i].map!"a + 1");
    }
    */
}