Hide

Students are hiding in several rooms. Each room has a current number of students and a maximum number of students who can sleep there. Some students must move to other rooms so that no room exceeds its limit.

The rooms are numbered from 1 to F, and P passages connect pairs of rooms. Any number of students may use the same passage at the same time, and every passage can be used in both directions. The time for one student to move along a path is the sum of the passage times on that path. Since all students can move simultaneously, the total moving time is the largest travel time used by any student who moves.

Some students may stay in their current room. Find the minimum total moving time needed to place all students without exceeding any room limit.

The first line contains the number of rooms F (1 ≤ F ≤ 200) and the number of passages P (1 ≤ P ≤ 1,500).

Each of the next F lines describes one room from room 1 through room F. Each line contains the current number of students in that room and the maximum number of students who can sleep there. Both values are integers between 0 and 1,000, inclusive.

Each of the next P lines contains the two room numbers connected by a passage and the time needed to pass through it. Each passage time is an integer not greater than 1,000,000,000.

Print the minimum total moving time needed to satisfy every room limit. If it is impossible, print -1.

In room 1, two students can stay, four students can move to room 2, and one student can move to room 3. The shortest route to room 3 takes 110 time units, so the total moving time is 110.