CF1076D Edge Deletion

题目描述

给一个$n$个点,$m$条边的无向简单带权连通图, 要求删边至最多剩余$k$条边.

定义"好点"是指删边后, 1号节点到它的最短路长度仍然等于原图最短路长度的节点.

最大化删边后的好点个数.

输入格式

第一行三个整数$n,m,k$.接下来$m$行每行三个整数, $u,v,w$, 分别为端点和边权.

输出格式

第一行一个整数$e, (0 \le e \le k)$, 需要保留的边数.

接下来一行$e$个整数, 保留的边的编号, 边是按输入顺序编号的, 但输出可以以任意顺序.

输入输出样例 #1

输入 #1

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

输出 #1

2
1 2 

输入输出样例 #2

输入 #2

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

输出 #2

2
3 2 

说明/提示

$n, m \le 3 \times 10^5$.