题目描述

每天，FJ 需要经过一些道路去检查牛棚 $n$ 里面的牛。农场上有 $m$ 条双向泥土道路，编号为 $1\sim m$。道路 $i$ 连接牛棚 $p_{1_i}$ 和 $p_{2_i}$。FJ 需要 $t_i$ 时间单位用道路 $i$ 从 $p_{1_i}$ 走到 $p_{2_i}$ 或者从 $p_{2_i}$ 走到 $p_{1_i}$。

他想更新一些路经来减少每天花在路上的时间。具体地说，他想更新 $k$ 条路经，将它们所须时间减为 $0$。帮助 FJ 选择哪些路经需要更新使得从 $1$ 到 $n$ 的时间尽量少。

输入格式

第一行：三个空格分开的数：$n,m,k$。 第 $2\sim m+1$ 行：第 $i+1$ 行有三个空格分开的数：$p_{1_i},p_{2_i},t_i$。

输出格式

• 第一行: 更新最多 $k$ 条路经后的最短路经长度。

4 4 1
1 2 10
2 4 10
1 3 1
3 4 100

1

数据规模与约定

对于 $100\%$ 的数据，$1\le m \le 50000$，$1 \leq p_{1_i} \leq n$，$1 \le p_{2_i}\le n$，$1 \le t_i \le 1\times 10^6$，$1 \le k \le 20$。

提示

样例中 $k$ 是 $1$，更新道路 $3->4$ 使得从 $3$ 到 $4$ 的时间由 $100$ 减少到 $0$。 最新最短路经是 $1->3->4$，总用时为 $1$ 单位。

题目来源

Usaco2009 Feb Gold