随机旅行

题目描述

Orange打算假期出门玩，由于他是某航司的白金卡会员，因此该航司为Orange推出了 $q$ 款特惠里程卡。

该航空公司的航线共覆盖 $n$ 个城市，共 $m$ 条航线。其中第 $i$ 款特惠里程卡可以用于从城市 $s_i$ 出发，飞往距离 $s_i$ 总里程不超过 $v_i$ 的城市(可以中转)。

现在，Orange决定从这 $q$ 款里程卡中随机购买一款，他想知道，自己能够到达不同城市个数的期望是多少？答案保留 $2$ 位小数。

输入格式

输入共 $m + q + 1$ 行：

第1行为三个整数 $n,m,q$，如题意所述。

接下来 $m$ 行，每行 $3$ 个整数 $u,v,w$，表示存在一条从 $u$ 到 $v$ 长度为 $w$ 的双向航线。

接下来 $q$ 行，每行 $2$ 个整数 $s, v$，表示第 $i$ 款里程卡的起点和总可行里程长度。

数据范围

$n \le 1000$ $m \le 5000$ $q \le 50000$ $w \le 10^5$ $v \le 10^9$

数据保证没有重边和自环。

输出格式

输出一个实数，表示答案。

样例 #1

样例输入 #1

3 2 3
1 2 1
2 3 1
2 1 1
2 0
1 1

样例输出 #1

2.00