CF1076D.Edge Deletion

You are given an undirected connected weighted graph consisting of $n$ vertices and $m$ edges. Let's denote the length of the shortest path from vertex $1$ to vertex $i$ as $d_i$.

You have to erase some edges of the graph so that at most $k$ edges remain. Let's call a vertex $i$ good if there still exists a path from $1$ to $i$ with length $d_i$ after erasing the edges.

Your goal is to erase the edges in such a way that the number of good vertices is maximized.

给你一个包含 $n$ 个顶点和 $m$ 条边的无向连通带权图。记从顶点 $1$ 到顶点 $i$ 的最短路径长度为 $d_i$。

你需要删除图中的一些边，使得剩余边数至多为 $k$ 条。若在删边后仍存在一条从顶点 $1$ 到顶点 $i$ 的长度恰好为 $d_i$ 的路径，则称顶点 $i$ 是“好”的。

你的目标是通过删边，使得“好”顶点的数量最大化。

The first line contains three integers $n$, $m$ and $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$) — the number of vertices and edges in the graph, and the maximum number of edges that can be retained in the graph, respectively.

Then $m$ lines follow, each containing three integers $x$, $y$, $w$ ($1 \le x, y \le n$, $x \ne y$, $1 \le w \le 10^9$), denoting an edge connecting vertices $x$ and $y$ and having weight $w$.

The given graph is connected (any vertex can be reached from any other vertex) and simple (there are no self-loops, and for each unordered pair of vertices there exists at most one edge connecting these vertices).

第一行包含三个整数 $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$ 的边。

给定的图是连通的（任意顶点均可从其余任意顶点到达），且是简单图（不存在自环，且对任意无序顶点对至多存在一条边连接这两个顶点）。

In the first line print $e$ — the number of edges that should remain in the graph ($0 \le e \le k$).

In the second line print $e$ distinct integers from $1$ to $m$ — the indices of edges that should remain in the graph. Edges are numbered in the same order they are given in the input. The number of good vertices should be as large as possible.

第一行输出 $e$ —— 图中应保留的边的数量（$0 \le e \le k$）。

第二行输出 $e$ 个互不相同的整数，取值范围为 $1$ 到 $m$ —— 表示应保留在图中的边的编号。边的编号顺序与其在输入中出现的顺序一致。应使“好顶点”的数量尽可能大。