# 寻找宝藏山

一天，你去了一个神秘的森林，在那里你遇到了一个神秘的老人。他告诉你，森林里有一座宝藏山，但是要想到达宝藏山，你必须先通过一些森林的入口。

这个老人给你了一张地图，地图上有若干个入口和宝藏山，每个入口都有一个花费。你可以从任意一个入口开始，然后经过一些入口，最终到达宝藏山。但是你有一个限制，你只能走 $K$ 步，如果走的步数超过了 $K$，那么你就无法到达宝藏山，也就无法获得宝藏。

你必须实现一个程序，接受用户输入的地图信息，并计算出，你能够到达宝藏山的最小花费。

## 输入描述

第一行包含三个整数 $N$、$M$ 和 $K$，$N$ 表示入口的个数、$M$ 表示边的个数、$K$ 表示最多走的步数。

接下来 $M$ 行，每行包含三个整数 $A$、$B$ 和 $C$，表示一条从 $A$ 到 $B$ 的有向边，边权为 $C$。

## 输出描述

输出一行，包含一个整数，表示你能够到达宝藏山的最小花费。

## 输入样例

5 10 6
1 2 3
1 2 3
1 2 3
1 2 3
1 2 3
5 2 3
2 3 4
2 1 1
2 3 4
3 4 5

## 输出样例

1061109567

## 提示

无