Easter Holidays Ski Journey

Scandinavians love to ski during the Easter holidays at a large ski resort. The resort has many lifts that carry skiers upward and slopes of various difficulty that are skied downward.

Per is a beginner and is afraid of lifts, yet he still wants to ski as much as possible. He wants to plan a ski journey that:

• starts at the bottom of some lift and returns to that same place;
• consists of exactly two phases: first he rides one or more lifts upward, then he skis all the way back down to the starting place using slopes only;
• is as little scary as possible, meaning the ratio of the time spent skiing on slopes to the time spent riding or waiting for lifts is as large as possible.

A resort has $n$ places, $m$ slopes, and $k$ lifts ($2 \le n \le 1000$, $1 \le m \le 1000$, $1 \le k \le 1000$). Each slope leads from a higher place to a lower place, and each lift leads from a lower place to a higher place (a lift cannot be ridden downward). It is guaranteed that at least one valid ski journey exists in every resort.

The first line contains the number of resorts to process. Each resort is described as follows. The first line contains three integers $n$, $m$, and $k$. The next $m$ lines each describe a slope with three integers: its upper place, its lower place (places are numbered from $1$ to $n$), and the time to ski down the slope (at most $10000$). The following $k$ lines each describe a lift with three integers: its lower place, its upper place, and the time to wait for and ride the lift up (at most $10000$). No two places are connected by more than one lift or by more than one slope.

For each resort, print on a single line the largest achievable scariness ratio as an irreducible fraction $p/q$. This ratio is the total time spent on slopes divided by the total time spent riding or waiting for lifts.