山路货运

题目背景

一支货运车队要在两座山城之间运送货物。山区公路年久失修，每条路都有自己的损耗值，车队最怕的就是沿途最糟糕的那几段路——车轴坏在路上，损失远比油钱大。

题目描述

山区公路网中有 $n$ 座城市，编号从 $1$ 到 $n$；城市之间有 $m$ 条双向公路，第 $i$ 条公路连接城市 $u_i$ 与 $v_i$，损耗值为 $w_i$。同一对城市之间可能有多条公路，也可能出现连接同一座城市的公路。

一条从城市 $1$ 到城市 $n$ 的路径由若干条公路首尾相接组成，路径允许重复经过同一座城市或同一条公路。把一条路径经过的所有公路的损耗值从大到小排列，其中第 $k$ 个值称为这条路径的第 $k$ 大损耗；若路径包含的公路不足 $k$ 条，则规定它的第 $k$ 大损耗为 $0$。

车队按如下次序挑选路线：

1. 在所有从 $1$ 到 $n$ 的路径中，先让第 $k$ 大损耗尽可能小，记这个最小值为 $X$；
2. 再在所有第 $k$ 大损耗恰好为 $X$ 的路径中，让沿途损耗值之和尽可能小，记这个最小总和为 $S$。

请你输出 $X$ 与 $S$。如果城市 $1$ 与城市 $n$ 之间不存在任何路径，输出 -1。

输入格式

从标准输入读入数据。

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

接下来 $m$ 行，每行三个整数 $u_i, v_i, w_i$，表示一条连接 $u_i$ 与 $v_i$、损耗值为 $w_i$ 的双向公路。

输出格式

输出到标准输出。

输出一行两个整数 $X$ 与 $S$；若不存在路径，输出 -1。

样例 1 输入

4 5 2
1 2 1
2 4 5
1 3 3
3 4 3
2 3 2

样例 1 输出

1 6

样例 1 解释

路径 $1 \to 2 \to 4$ 经过损耗值为 $1$ 与 $5$ 的两条公路，第 $2$ 大损耗为 $1$，损耗值之和为 $6$。

路径 $1 \to 3 \to 4$ 的第 $2$ 大损耗为 $3$；路径 $1 \to 2 \to 3 \to 4$ 经过三条公路，损耗值为 $1, 2, 3$，第 $2$ 大损耗为 $2$。

可以验证不存在第 $2$ 大损耗为 $0$ 的路径，因此 $X = 1$；在所有第 $2$ 大损耗为 $1$ 的路径中，损耗值之和最小为 $6$，输出 1 6。

样例 2 输入

3 1 1
1 2 4

样例 2 输出

-1

数据范围

特殊性质 A：$k = 1$。

特殊性质 B：所有公路的损耗值都相等。

对于所有测试数据，$2 \le n \le 20000$，$1 \le m \le 10^5$，$1 \le k \le 10$，$1 \le w_i \le 10^9$。$X$ 与 $S$ 都可能超过 $2^{31} - 1$。

提交说明

本题使用标准输入输出。程序应从标准输入读入数据，并将答案输出到标准输出。