Edge Deletion

题意翻译

## 题目描述 给一个$n$个点,$m$条边的无向简单带权连通图, 要求删边至最多剩余$k$条边. 定义"好点"是指删边后, 1号节点到它的最短路长度仍然等于原图最短路长度的节点. 最大化删边后的好点个数. ## 输入格式 第一行三个整数$n,m,k$.接下来$m$行每行三个整数, $u,v,w$, 分别为端点和边权. ## 输出格式 第一行一个整数$e, (0 \le e \le k)$, 需要保留的边数. 接下来一行$e$个整数, 保留的边的编号, 边是按输入顺序编号的, 但输出可以以任意顺序. ## 数据范围 $n, m \le 3 \times 10^5$.

题目描述

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.

输入输出格式

输入格式

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).

输出格式

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.

输入输出样例

输入样例 #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