题目描述

给定一个节点 $1$ 和节点 $N$ 连通的正权无向图，请你删除不超过 $K$ 条边，使得节点 $1$ 和节点 $N$ 仍然连通的同时，这两点之间的最短路尽可能长 。

输入格式

本题为提交答案试题，输入文件（shortest1.in~shortest10.in）请在链接中下载。

输入文件 shortest*.in 的第一行包含三个正整数 $N,M,K$。其中 $N$ 表示节点数，$M$ 表示边数，节点的编号由 $1$ 至 $N$，边的编号由 $1$ 至 $M$。接下来 $M$ 行，

每行三个正整数 $u,v,w$，表示有一条连接节点 $u$ 和节点 $v$ 的边，权值为 $w$。

输出格式

输出文件 shortest*.out 的第一行包含一个非负整数 $T$，表示需要删掉的边数。

接下来 $T$ 行，每行一个 $1$ 到 $M$ 之间的整数 $x$，表示删掉输入中的第 $x$ 条边。你需要保证这 $T$ 个整数互不相同。

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

1
3

提示

样例说明

样例中从节点 $1$ 到 $3$ 的最短路径长度为 $1$，删去第三条边之后，最短路径长度为 $2$。

评分标准

对于每个测试点，设有评分四个参数 $s_1,s_2,s_3,s_4$。假设你的方案的最短路为 $\textit{ans}$。

如果你没有输出，或者输出不合法，或者最短路不存在，得 $0$ 分。

如果最短路存在，得 $1$ 分。

如果 $\textit{ans}\geq s_1$，得 $3$ 分。

如果 $\textit{ans}\geq s_2$，得 $5$ 分。

如果 $\textit{ans}\geq s_3$，得 $8$ 分。

如果 $\textit{ans}=s_4$，得 $10$ 分。

如果 $\textit{ans}>s_4$，得 $12$ 分。

取满足条件的分数中的最高得分为该测试点你的得分。

如何测试你的输出

首先先编译 checker.cpp。

在你的目录下有一个名为 checker 的程序可以用来检查你的输出，你可以在终端中使用以下命令来检查你的输出：

./checker N

其中 $N$ 为测试点的编号；例如，要测试第 $3$ 个测试点可以使用

./checker 3

该程序会检测你的输出方案是否合法。如果方案合法，程序还会给出该方案的最短路的长度值。

特别提示

请妥善保存输入文件和你的输出文件，及时备份，以免误删。