题目描述

Barica 是一只非同寻常的青蛙。她住在一个池塘里，有 $N$ 片漂浮在水面上的荷叶。这些荷叶的编号为 $1$ 到 $N$，位置可以用一对坐标表示。Barica 可以在这些荷叶上跳来跳去，但是她害怕斜着跳和朝负方向跳。

准确的说，她可以从坐标 $(x_1,y_1)$ 跳到另一个坐标 $(x_2,y_2)$ 仅当：

• $x_2>x_1$ 且 $y_2=y_1$ 或者

• $y_2>y_1$ 且 $x_2=x_1$。

对于每一片荷叶，我们知道其附近的苍蝇数量。Barika 可以吃掉所有在她荷叶附近的苍蝇。

Barica 每吃一只苍蝇会获得 $1$ 个单位的能量，每进行一次跳跃消耗 $K$ 个单位的能量。如果 Barica 没有足够的能量，她就不能进行跳跃。

Barica 想通过 $1$ 号植物到达 $N$ 号植物，并获得尽可能多的能量。Barica 开始时没有能量，必须通过吃掉 $1$ 号植物附近的苍蝇来获取能量。

找到使得 Barica 达到目标的一种可行路径。

输入格式

第一行，两个整数 $N$ 和 $K$。

接下来 $N$ 行，每行包含三个整数 $x_i$，$y_i$ 和 $z_i$，表示第 $i$ 号荷叶的坐标为 $(x_i,y_i)$，且其附近有 $z_i$ 只苍蝇。

输出格式

第一行，输出到达终点后能量单位数量。

第二行，输出一个整数 $L$，表示 Barica 需要经过的植物个数。必须包含 $1$ 号和 $N$ 号植物。

接下来 $L$ 行，依次输出 Barica 需要经过的植物坐标。

6 5
1 1 5
2 1 5
1 2 4
2 3 5
3 2 30
3 3 5 

5
4
1 1
2 1
2 3
3 3 

8 10
1 1 15
2 2 30
1 2 8
2 1 7
3 2 8
2 3 7
4 2 100
3 3 15

36
5
1 1
1 2
2 2
3 2
3 3

9 5
5 5 10
6 5 2
7 5 1
5 6 2
6 6 6
7 6 2
5 7 1
6 7 2
7 7 1 

2
3
5 5
7 5
7 7 

提示

对于 $100\%$ 的数据，$2\le N\le 3\times 10^5$，$1\le K\le 1000$，$0\le x_i,y_i\le 10^5$，$0\le z_i\le 1000$。

输入数据保证有解，但不保证有唯一解。

本题分值按照原比赛设置，满分 $70$ 分。