Description

国王决定奖励你一些城市，你可以选择哪些是自己的！但你不可以选择从首都可以到达的城市。为了满足这个条件，必须毁坏一些道路。每条道路都是单向的。有些城市是留给国王的，所以即使从首都无法到达这些城市，也不可以选。首都的编号为$1$。你的最终收入等于你所选择的城市的总价值减去摧毁道路的成本。

Input

第$1$行包含测试用例的数量$T$ $（$$T$ $≤$$2$$0$$）$。每个测试用例的第$2$行都以$3$个整数$n$ 、$m$ 、$f$ $（$$1$$≤$$f$ $<$$n$ $≤$$1$$0$$0$$0$，$1$$≤$$m$ $<$$1$$0$$0$$0$$0$$0$$）$开始，表示城市数量、道路数量和可以选择的城市数量。城市编号为$1$～$n$，道路编号为$1$～$m$ 。在以下$m$ 行中每行都包含三个整数$u$ 、$v$ 、$w$ ，表示从城市$u$ 到城市$v$ 的道路，成本为$w$ 。以下$f$ 行中的每一行都包含两个整数$u$ 和$w$ ，表示可选城市$u$ ，价值为$w$ 。

Output

对每个测试用例，第$1$行都输出测试用例号和最大收益，第$2$行都输出销毁的道路数量$e$ ，后面紧跟$e$ 个整数，表示已销毁道路的编号，与它们的输入顺序相同。若有多个解决方案，则任意一个都可以。

Samples

2
4 4 2
1 2 2
1 3 3
3 2 4
2 4 1
2 3
4 4
4 4 2
1 2 2
1 3 3
3 2 1
2 4 1
2 3
4 4

Case 1: 3
1 4
Case 2: 4
2 1 3