import std.stdio;
import std.string;
import std.conv;
import std.typecons;
import std.algorithm;
import std.functional;
import std.bigint;
import std.numeric;
import std.array;
import std.math;
import std.range;
import std.container;

long INF = 1L<<60;
int N, K;
bool[][] passable;
long[] c, r;
void main() {
    string[] input = readln.split;
    N = input[0].to!int;
    K = input[1].to!int;
    passable = new bool[][](N, N);
    c = new long[N];
    r = new long[N];
    foreach(int i; 0..N) {
        input = readln.split;
        c[i] = input[0].to!long;
        r[i] = input[1].to!long;
    }
    foreach(int i; 0..K) {
        input = readln.split;
        passable[input[0].to!int-1][input[1].to!int-1] = true;
        passable[input[1].to!int-1][input[0].to!int-1] = true;
    }

    Node[] nodes = new Node[N];
    foreach(int i; 0..N) {
        nodes[i] = new Node(i, c[i]);
    }
    auto queue = new BinaryHeap!(Array!Node, "a.value>=b.value")();
    nodes.front.value = 0;
    queue.insert(nodes.front);
    while(!queue.empty) {
        queue.length.writeln;
        Node e = queue.front;
        queue.removeFront;
        e.done = true;
        foreach(int i; 0..N) {
            if (!nodes[i].done && passableOnce(e.index, i)) {
                if (e.value+e.cost < nodes[i].value) {
                    nodes[i].value = e.value+e.cost;
                    queue.insert(nodes[i]);
                }
            }
        }
    }
    nodes.back.value.writeln;
}
bool passableOnce(int from, int to) {
    long[] ary = new long[N];
    ary[] = INF;
    ary[from] = 0;
    auto list = DList!(int)(from);
    while(!list.empty) {
        int i = list.front;
        list.removeFront;
        if (ary[i] >= r[from]) break;
        foreach(int j; 0..N) {
            if (passable[i][j] && ary[j] == INF) {
                ary[j] = ary[i]+1;
                list.insert(j);
            }
        }
    }
    return ary[to] < INF;
}
class Node{
    int index;
    long cost;
    bool done = false;
    long value;
    this(int index, long cost) {
        this.index = index;
        this.cost = cost;
        this.value = INF;
    }
}