G. Torque Transmission
time limit per test
3 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

In a mechanical power transmission system, several gears are connected by shafts. Each gear transmits torque to the next one. However, due to frictional losses and imperfect contact, only a certain percentage of torque is actually transferred from one gear to another.

The system can be modeled as a directed graph:

  • Each gear is a node.
  • Each shaft is a directed edge with an efficiency percentage (between 0 and 100).

The torque delivered to the next gear is: $$$$$$ T_{next} = T_{current} \times \frac{\text{efficiency}}{100}. $$$$$$

Your job is to compute the maximum possible torque that can be delivered to a specified target gear, starting from the input gear.

Input

The first line contains three integers $$$n, m, q$$$:

  • $$$n$$$: number of gears.
  • $$$m$$$: number of shafts.
  • $$$q$$$: number of queries.

The next $$$m$$$ lines each contain three integers: $$$u, v, e$$$ meaning there is a shaft from gear $$$u$$$ to gear $$$v$$$ with efficiency $$$e\%$$$.

Each of the next $$$q$$$ lines contains three integers: $$$s, t, T$$$, where torque $$$T$$$ is applied to gear $$$s$$$. You must compute the maximum torque that can reach gear $$$t$$$.

  • $$$1 \le n \le 1000$$$.
  • $$$1 \le m \le 5000$$$.
  • $$$1 \le q \le 100$$$.
  • $$$1 \leq u,v,s,t \leq n$$$.
  • $$$u \neq v$$$.
  • $$$1 \leq e \leq 100$$$.
  • $$$1 \leq T \leq 10^6$$$.
  • An output is considered correct if it has an absolute or relative error of at most $$$10^{-6}$$$.
Output

For each query, output the maximum torque that can be delivered to the target gear. If the target gear is unreachable, output 0.

Example
Input
5 6 2
1 2 90
2 3 80
1 4 50
4 5 70
2 5 60
3 5 85
1 5 1000
2 4 500
Output
612.000000
0