Background

This was supposed to be a very simple problem. However, the cows got very confused because of the rain and cannot finish the calculation, so the task is handed to you. (For the reason the cows are confused, see the problem description.)

Problem Description

There are $n$ fields on a farm. One afternoon, a herd of cows is grazing in the fields. They are spread across many fields of the farm, which are connected by $m$ undirected roads, each with a different length.

Suddenly, heavy rain falls. The cows are very confused and want to find shelter quickly. It is known that each field has a barn, but each barn can only hold a limited number of cows. If the number of cows exceeds this capacity, the extra cows must go to other fields to shelter. Moving a distance of $1$ costs time $1$. The cows want to know the minimum time needed for all of them to get into barns, i.e., the minimum time the last cow needs to get into a barn.

Input Format

• The first line contains two integers, the number of fields $n$ and the number of roads $m$.
• The next $n$ lines each contain two integers. On the $(i + 1)$-th line, the integers $s_i, p_i$ denote the number of cows in field $i$ and the maximum capacity of the barn at that field, respectively.
• The next $m$ lines each contain three integers $u, v, w$, indicating there is an undirected road of length $w$ connecting $u$ and $v$.

Output Format

Output a single integer, the minimum time required for all cows to get into barns. If it is impossible for all cows to find shelter, output $-1$.

3 4 
7 2 
0 4 
2 6 
1 2 40 
3 2 70 
2 3 90 
1 3 120

110

Hint

Sample Input/Output 1 Explanation:

The two cows at node $1$ go directly into barn $1$. Among the remaining $5$ cows, $4$ run to node $2$, and one goes along $1 \to 2 \to 3$ to get into barn $3$. The $2$ cows at node $3$ also go directly into its barn. In this arrangement, the slowest cow spends time $110$.

Constraints:

For $100\%$ of the data, it is guaranteed that:

• $1 \leq n \leq 200$, $1 \leq m \leq 1500$.
• $1 \leq u, v \leq n$, $1 \leq w \leq 10^{15}$, $1 \leq s_i, p_i \leq 10^{16}$.

Translated by ChatGPT 5