Marisa and Reimu are going to a park. The park has $n$ locations, where playing at the $i$-th location takes $t_i$ minutes, and the joy of Marisa and Reimu increases by $a_i$ and $b_i$, respectively.
There are $m$ two-way paths connecting the locations in the park. The $i$-th path connects locations $u_i$ and $v_i$, and traveling along this path takes $w_i$ minutes.
Marisa and Reimu have $k$ minutes to enjoy the park. They will start at a random location. After playing at a location, they will randomly choose the next location that is directly connected to their current location. If they cannot move to another location or run out of time, they will stop playing.
Find the expected value of the joy of Reimu and Marisa after their trip.
### Input
- The first line contains three integers $n$, $m$, and $k$.
- The next $n$ lines each contain three integers $t_i$, $a_i$, and $b_i$.
- The next $m$ lines each contain three integers $u_i$, $v_i$, and $w_i$.
### Output
Print two floating-point numbers rounded **exactly** to 5 decimal places, representing the expected joy of Marisa and Reimu, respectively.
### Constraints
- $1 \leq n \leq 100$
- $60 \leq k \leq 480$
- $10 \leq t_i \leq 60$
- $1 \leq a_i, b_i \leq 100$
- $1 \leq w_i \leq 15$
### Example
Input:
```
5 4 60
26 13 84
29 37 89
15 14 70
23 16 63
51 71 15
2 1 6
3 1 7
4 3 2Marisa and Reimu are going to a park. The park has $n$ locations, where playing at the $i$-th location takes $t_i$ minutes, and the joy of Marisa and Reimu increases by $a_i$ and $b_i$, respectively.
There are $m$ two-way paths connecting the locations in the park. The $i$-th path connects locations $u_i$ and $v_i$, and traveling along this path takes $w_i$ minutes.
Marisa and Reimu have $k$ minutes to enjoy the park. They will start at a random location. After playing at a location, they will randomly choose the next location that is directly connected to their current location. If they cannot move to another location or run out of time, they will stop playing.
Find the expected value of the joy of Reimu and Marisa after their trip.
### Input
- The first line contains three integers $n$, $m$, and $k$.
- The next $n$ lines each contain three integers $t_i$, $a_i$, and $b_i$.
- The next $m$ lines each contain three integers $u_i$, $v_i$, and $w_i$.
### Output
Print two floating-point numbers rounded **exactly** to 5 decimal places, representing the expected joy of Marisa and Reimu, respectively.
### Constraints
- $1 \leq n \leq 100$
- $60 \leq k \leq 480$
- $10 \leq t_i \leq 60$
- $1 \leq a_i, b_i \leq 100$
- $1 \leq w_i \leq 15$
### Example
Input:
```
5 4 60
26 13 84
29 37 89
15 14 70
23 16 63
51 71 15
2 1 6
3 1 7
4 3 2
5 3 9
```
Output:
```
40.10000 113.90000
```
5 3 9
```
Output:
```
40.10000 113.90000
```
