P6768 [USACO05MAR] Ombrophobic Bovines Shivering Cows.

FJ’s cows are very afraid of getting rained on, which makes them shiver. They plan to install a rain alarm and arrange an evacuation plan. They need to compute the minimum time needed to get all cows into shelters. The cows graze on $F$ fields on the farm. There are $P$ bidirectional roads connecting these fields. The roads are wide, so an unlimited number of cows can pass through them. Each field has a shelter with a certain capacity, and cows can enter the shelter on the same field instantly. Compute the minimum time so that every cow can enter a shelter.

Line $1$: two integers $F$ and $P$. Lines $2$ to $F+1$: on line $i+1$, there are two integers describing field $i$. The first is the number of cows on the field, and the second is the shelter capacity on that field. Both integers are between $0$ and $1000$. Lines $F+2$ to $F+P+1$: each line contains three integers describing a road: the two endpoints, and the time needed to travel along this road (between $1$ and $10^9$).

One integer, the minimum time. If it is impossible to get all cows into shelters, output $-1$.

Constraints: for $100\%$ of the testdata, $1 \le F \le 200$, $1 \le P \le 1500$. Translated by ChatGPT 5