题目描述

游乐园被描述成一张 $n$ 个点，$m$ 条边的无向图（无重边，无自环）。每个点代表一个娱乐项目，第 $i$ 个娱乐项目需要耗费 $c_i$ 分钟的时间，会让小 y 和妹子的开心度分别增加 $h1_i , h2_i$，他们俩初始的开心度都是 $0$。每条边代表一条路，第 $i$ 条边连接编号为 $x_i , y_i$ 的两个娱乐项目，从 $x_i$ 走到 $y_i$ 或者从 $y_i$ 走到 $x_i$ 耗费的时间都是 $t_i$ 分钟。小 y 和妹子预计在游乐园里玩 $k$ 分钟。最开始的时候，小 y 和妹子会等概率的随机选择一个娱乐项目开始玩，每玩完一个项目后，小 y 和妹子会等概率的随机选择一个可以从当前项目直达的且来得及玩的项目作为下一个项目。如果玩完一个项目后周围没有可以直达的且来得及玩的项目，小 y 和妹子就会提前结束游玩。 请你分别计算小 y 和妹子在游玩结束后开心度的期望。

输入格式

第一行给出三个空格隔开的整数，分别表示 $n,m,k$。

接下来的 $n$ 行，每行三个空格隔开的整数，分别表示 $c_i,h1_i,h2_i$。

接下来的 $m$ 行，每行三个空格隔开的整数，分别表示 $x_i,y_i,t_i$。

输出格式

两个用空格隔开的实数，分表表示小 y 和妹子开心度的期望，精确到小数点后 $5$ 位。

5 4 60
25 12 83
30 38 90
16 13 70
22 15 63
50 72 18
2 1 7
3 1 7
4 3 1
5 3 10

39.20000 114.40000

提示

$0<n \leq 100, 1 \times 60 \leq k \leq 8 \times 60$。

$10 \leq c_i \leq 60, 0 < h1_i, h2_i \leq 100$。