每周，Karlijn 和她的队友们都会参加大学的程序设计竞赛训练。长时间的思考和编码非常消耗体力，他们需要大量的零食来支撑训练。他们已经分好了带零食的任务：另外两人带了焦糖煎饼和咸味棒，而 Karlijn 的任务是提供姜饼（kruidnoten）。

她通常在从家去大学的路上顺便买这些零食。她家乡的自行车网络由若干个交叉路口组成，这些路口之间由不同长度的自行车道相连。交叉路口编号为 $1$ 到 $n$。Karlijn 的家在交叉路口 $1$，大学在交叉路口 $n$。

有许多商店出售姜饼，但其中一些经常缺货。Karlijn 希望尽快到达大学，所以她习惯在离家前上网查询哪些商店还有姜饼。利用这些信息，她会选择一条经过某家有货商店的最短路径。图 K.1 展示了一个例子。

图 K.1：来自样例输入 1 的一种可能情况，并非每家商店都有姜饼库存。在这种情况下，Karlijn 在交叉路口 3 的商店购买姜饼，最短路径长度为 11。

现在，她想知道她通常应该为去训练的路上预留多少时间。根据长期的经验，Karlijn 知道每家商店有货的概率。特别地，她观察到每家商店的姜饼库存是相互独立的。如果她想在去大学的路上访问某家有货的商店，那么从 Karlijn 家到大学的最短路径的期望长度是多少？

输入格式

输入包含： 第一行包含三个整数 $n, m$ 和 $k$ ($2 \le n \le 2 \cdot 10^5, 1 \le m \le 2 \cdot 10^5, 1 \le k \le n$)，分别表示交叉路口、自行车道以及可能出售姜饼的商店的数量。 $m$ 行，每行包含三个整数 $i, j$ 和 $\ell$ ($1 \le i, j \le n, i \neq j, 1 \le \ell \le 10^6$)，表示交叉路口 $i$ 和 $j$ 之间由一条长度为 $\ell$ 的自行车道相连。保证每对交叉路口之间最多只有一条自行车道。此外，保证可以通过自行车从任意一个交叉路口到达其他任何交叉路口。 * $k$ 行，每行包含一个整数 $i$ ($1 \le i \le n$) 和一个浮点数 $p$ ($0 < p \le 1$，小数点后最多四位)，表示在交叉路口 $i$ 有一家商店，且该商店仍有姜饼的概率为 $p$。保证每个交叉路口最多只有一家姜饼商店。

输出格式

如果 Karlijn 在路上无法买到任何姜饼的事件概率 $> 0$，则输出 “impossible”。否则，输出她在路上买到姜饼的情况下，从家到大学的最短路径的期望长度。

你的答案应具有不超过 $10^{-6}$ 的绝对或相对误差。

样例

样例输入 1

5 5 3
1 2 6
3 1 4
4 5 2
1 4 1
3 4 5
2 1.0
3 0.4
5 0.1

样例输出 1

12.36

样例输入 2

6 5 2
1 2 1
1 3 1
4 5 3
5 6 1
6 3 2
1 0.6283
4 0.3142

样例输出 2

impossible