每周，Karlijn 和她的队友们都会参加大学的编程竞赛训练。长时间思考和编程非常耗费精力，他们需要大量零食来度过训练时间。他们分工明确：其他两人负责带华夫饼和盐棒，而 Karlijn 的任务是提供荷兰小饼干（kruidnoten）。 她通常会在从家到大学的路上，训练前购买这些饼干。她家乡的自行车网络由多个交叉路口组成，这些交叉路口通过不同长度的自行车道连接。交叉路口编号从 \(1\) 到 \(n\)。Karlijn 的家在交叉路口 \(1\)，大学在交叉路口 \(n\)。 有多家商店出售荷兰小饼干，但有些商店经常缺货。Karlijn 希望尽快到达大学，因此她习惯在出门前在线查看哪些商店还有库存。利用这些信息，她会选择一条经过某些有库存商店的最短路径。图 K.1 展示了一个示例。  现在，她想知道通常需要为去训练的路程预留多少时间。根据长期经验，Karlijn 知道每家商店缺货的概率。特别是，她观察到每家商店的库存情况是独立的。如果 Karlijn 希望在去大学的路上经过某些有库存的商店，那么她选择的最短路径的期望长度是多少？

一行，包含三个整数 $n$、$m$ 和 $k(2 \leq n \leq 2 \cdot 10^5$，$1 \leq m \leq 2 \cdot 10^5$，$1 \leq k \leq n)$，分别表示交叉路口的数量、自行车道的数量以及可能出售荷兰小饼干的商店数量。 $m$ 行，每行包含三个整数 $i$、$j$ 和 $\ell(1 \leq i, j \leq n, i \neq j, 1 \leq \ell \leq 10^6)$，表示交叉路口 $i$ 和 $j$ 之间有一条长度为 $\ell$ 的自行车道。保证每对交叉路口之间最多有一条自行车道，并且可以从任意交叉路口骑车到达其他任意交叉路口。 $k$ 行，每行包含一个整数 $i(1 \leq i \leq n)$和一个浮点数 $p(0 < p \leq 1)$，小数点后最多四位，表示在交叉路口 $i$ 有一家商店，且该商店仍有荷兰小饼干库存的概率为 $p$。保证每个交叉路口最多有一家荷兰小饼干商店。

如果 Karlijn 无法在去大学的路上买到任何荷兰小饼干的概率大于 $0$，则输出“impossible”。否则，输出她在路上买到荷兰小饼干的情况下，从家到大学的最短路径的期望长度。 答案的绝对误差或相对误差应不超过 $10^{-6}$。

样例输入 1 中的一个可能情况，并非所有商店都有荷兰小饼干库存。在这种情况下，Karlijn 在交叉路口 3 的商店购买了荷兰小饼干，最短路径的长度为 11

NWERC 2024 K