Problem11360--边的删减

11360: 边的删减

[Creator : ]
Time Limit : 1.000 sec  Memory Limit : 512 MiB

Description

给定一个由 $n$ 个点和 $m$ 条边组成的无向连通加权图。

设点 $1$ 到点 $i$ 的最短路径长度为 $d_i$。

现在,你需要删掉图中的一些边,使得图中最多保留 $k$ 条边。

如果在删边操作全部完成后,点 $1$ 到点 $i$ 的最短路径长度仍为 $d_i$,则称点 $i$ 是一个优秀点。

你的目标是通过合理进行删边操作,使得优秀点的数量尽可能大。

Input

第一行包含三个整数 $n,m,k$。

接下来 $m$ 行,每行包含三个整数 $x,y,w$,表示点 $x$ 和点 $y$ 之间存在一条长度为 $w$ 的边。

保证给定无向连通图无重边和自环。

Output

第一行包含一个整数 $e$,表示保留的边的数量 $(0≤e≤k)$。

第二行包含 $e$ 个不同的 $1\sim m$ 之间的整数,表示所保留的边的编号。

按输入顺序,所有边的编号从 $1$ 到 $m$。

你提供的方案,应使得优秀点的数量尽可能大。

如果答案不唯一,则输出任意满足条件的合理方案均可。

Constraints

对于全部测试点,$2≤n≤10^5,\ 1≤m≤10^5,\ n−1≤m,\ 0≤k≤m,\ 1≤x,y≤n,\ x≠y,\ 1≤w≤10^9$。

Sample 1 Input

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

Sample 1 Output

2
1 2

Sample 2 Input

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

Sample 2 Output

2
3 2

HINT

AcWing.

Source/Category