链接: https://cses.fi/problemset/task/1724

板块: Mathematics

时限: 1.00 s ｜ 内存: 512 MB

题目描述

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

输入

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

随后有 $m$ 行描述边。每行包含三个整数 $a$、$b$ 和 $c$：表示存在一条从节点 $a$ 到节点 $b$、权值为 $c$ 的边。

输出

输出最短路径长度。若不存在这样的路径，则输出 $-1$。

数据范围

$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$

样例输入

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

样例输出

27