给你一个无向连通加权图,由 $$$n$$$ 个顶点和 $$$m$$$ 个边组成。我们将从顶点 $$$1$$$ 到顶点 $$$i$$$ 的最短路径的长度表示为 $$$d_i$$$。
您必须擦除图形的一些边,以便最多保留 $$$k$$$ 边。如果在删除边之后仍然存在从 $$$1$$$ 到 $$$i$$$ 且长度为 $$$d_i$$$ 的路径,我们称顶点 $$$i$$$ 为好。
您的目标是以最大化好顶点数量的方式擦除边缘。
输入
第一行包含三个整数 $$$n$$$、$$$m$$$ 和 $$$k$$$ ($$$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$$$) —分别是图中的顶点数和边数,以及图中可以保留的最大边数。
接下来是 $$$m$$$ 行,每行包含三个整数 $$$x$$$、$$$y$$$、$$$w$$$ ($$$1 \le x, y \le n$$$, $$$x \ne y$$$, $$$1 \le w \le 10^9$$$),表示连接顶点 $$$x$$$ 和$$$y$$$ 且重量为$$$w$$$。
给定的图是连通的(任何顶点都可以从任何其他顶点到达)并且简单(没有自环,并且对于每对无序顶点,最多存在一条连接这些顶点的边)。
输出
在第一行打印 $$$e$$$ — 图中应保留的边数 ($$$0 \le e \le k$$$)。
在第二行中打印 $$$e$$$ 从 $$$1$$$ 到 $$$m$$$ 的不同整数 - 应保留在图中的边的索引。边的编号顺序与输入中给出的顺序相同。好的顶点数量应该尽可能多。
示例
输入 #1
3 3 2 1 2 1 3 2 1 1 3 3
输出 #1
2 1 2
输入 #2
4 5 2 4 1 8 2 4 1 2 1 3 3 4 9 3 1 5
输出 #2
2 3 2