你是国王麾下的一名工程师。国王要求你建造一座城堡。该项目已接近尾声。已知城堡将包含 $n$ 座塔和 $m$ 道墙，每道墙连接某一对塔。塔可以看作平面上的点，墙可以看作连接塔的线段。该规划满足以下若干合理的假设：

• 没有墙连接塔与其自身；
• 任意一对塔之间最多只有一道墙；
• 不同的墙除了在塔处相交外，在其他任何地方都不相交；
• 没有两座塔位于相同的位置；
• 没有墙会穿过除其端点以外的任何塔。

你的任务是选择一些墙并在其中建造大门。在此之后，城堡每一道墙的两侧都必须能够从外部通过大门进入。由于地形不同，在不同的墙上建造大门需要花费不同的金额。完成任务所需的最少金额是多少？

输入格式

第一行包含两个数字 $n, m$ —— 分别为塔的数量和墙的数量 ($1 \le n, m \le 10^5$)。

接下来的 $n$ 行，每行包含两个整数 $x_i, y_i$，表示第 $i$ 座塔建造在点 $(x_i, y_i)$ 处。坐标的绝对值不超过 $10^6$。

接下来的 $m$ 行，每行包含三个整数 $u_i, v_i, c_i$ ($1 \le u_i, v_i \le n, 1 \le c_i \le 10^6$)，表示在塔 $u_i$ 和 $v_i$ 之间有一道墙，且在这道墙上建造大门的费用为 $c_i$。

输出格式

首先，输出一个数字：建造所有必要大门所需的最少金额。然后输出一个数字 $k$，表示要建造的大门数量。接着输出 $k$ 对数字，表示根据你的方案，在哪些塔之间连接的墙上建造了大门。

样例

输入 1

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

输出 1

1
1
1 2

输入 2

4 5
1 0
2 1
1 2
0 1
1 2 1
2 3 2
3 4 3
4 1 4
1 3 5

输出 2

4
2
3 4
1 2