题目背景

翻译自 CSES-1724 题。

题目描述

考虑一个有向带权图，该图有 $n$ 个节点和 $m$ 条边。你的任务是计算从节点 $1$ 到节点 $n$ 的路径，且路径的长度恰好为 $k$ 条边的最短路径长度。

输入格式

第一行输入三个整数 $n，m，k$：分别表示节点数、边数和路径的长度。节点编号为 $1,2,\ldots,n$。

接下来的 $m$ 行描述了每一条边，每行包含三个整数 $a,b,c$，表示从节点 $a$ 到节点 $b$ 有一条带权重 $c$ 的有向边。

输出格式

输出从节点 $1$ 到节点 $n$ 的路径长度的最小值，路径的长度恰好为 $k$ 条边。如果没有这样的路径，输出 $-1$。

样例

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

8

数据范围

• $1 \le n \le 100$
• $1 \le m \le n(n-1)$
• $1 \le k \le 10^9$
• $1 \le a,b \le n$
• $1 \le c \le 10^9$