题目描述

给定一张有 $n$ 个点和 $m$ 条边的无向图。将从点 $1$ 至点 $i$ 的最短路长度记为 $d_i$。

你需要从图上删去一些边，使得图上最多剩余 $k$ 条边。我们称一个节点 $i$ 是一个好点当且仅当在所有删边操作完成后，仍存在一条从 $1$ 至 $i$ 的路径使得其长度等于 $d_i$。

你的目标是构造一种如上的删除方案，使得剩余的好点最多。

输入格式

第一行包含三个整数 $n,m,k\$ 表示图上的点数，边数和最多能剩余的边数。

接下来 $m$ 行，每行包含三个整数 $x,y,w\$，表示一条从 $x$ 到 $y$，权值为 $w$ 的边。

保证给定的图是联通的，无重边无自环的简单图。

输出格式

第一行输出一个整数 $e\ (0 \le e \le k)$，表示需要保留的边数（你需要保证 $0\le e\le k$）。

接下来一行输出 $e$ 个在 $1$ 至 $m$ 之间的不同整数，表示保留边的编号（按输入顺序编号，从 $1$ 开始，但可以以任意顺序输出）。

3 3 2
1 2 1
3 2 1
1 3 3

2
1 2 

4 5 2
4 1 8
2 4 1
2 1 3
3 4 9
3 1 5

2
3 2 

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

0

数据范围

$(2 \le n \le 3 \cdot 10^5,\ 1 \le m \le 3 \cdot 10^5,\ n - 1 \le m,\ 0 \le k \le m)$

$(1 \le x, y \le n,\ x \ne y,\ 1 \le w \le 10^9)$