Rain Shelter Retreat

Farmer John's cows are terrified of getting wet in the rain, and they shudder at the thought of it. To prepare for such an event, FJ plans to install a rain alarm and execute a retreat plan. The cows are grazing in F fields, and there are P bidirectional roads connecting these fields. Each field has a rain shelter with a limited capacity. When the alarm rings, the cows have to move via the roads (which have travel times) so that every cow can take shelter. Cows can enter a shelter instantly as soon as they reach the field with the shelter.

Your task is to compute the minimum time T required so that every cow gets into a shelter. Formally, if we denote the time needed for a cow to go from field i to field j by d(i, j) (using the shortest path over the roads), a cow initially in field i can use the shelter in field j only if $$d(i, j) \le T.$$ Each field i initially contains a certain number of cows and its shelter can accommodate a fixed number of cows. It is guaranteed that the total number of cows equals the total shelter capacity.

Input Format: The first line contains two integers F and P. The next F lines each contain two integers, representing the number of cows in the field and the shelter capacity of that field respectively. The following P lines each contain three integers u v t indicating that there is a bidirectional road between fields u and v with travel time t (u and v are 1-indexed).

Output Format: Output a single integer, the minimum time required so that every cow can reach a shelter.

Constraints: It is guaranteed that the sum of the cows over all fields equals the sum of the shelter capacities. You may assume that cows may move along a road even if many cows do so simultaneously (i.e. the roads have infinite capacity), and entering a shelter is instantaneous.

inputFormat

The first line contains two integers F and P separated by a space.

The next F lines each contain two integers: the number of cows in the field and the shelter capacity of that field.

The following P lines each contain three integers u, v, and t representing a bidirectional road connecting fields u and v with travel time t.

It is guaranteed that the total number of cows equals the total shelter capacity.

outputFormat

Output a single integer representing the minimum time required for every cow to be sheltered.

sample

3 3
3 3
2 2
1 1
1 2 5
2 3 5
1 3 12

0