#T2183. 图路径 II(Graph Paths II)

图路径 II(Graph Paths II)

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

板块: Mathematics

时限: 1.00 s | 内存: 512 MB

题目描述

考虑一个有 nn 个节点和 mm 条边的带权有向图。你的任务是计算从节点 11 到节点 nn、恰好经过 kk 条边的最短路径长度。

输入

第一行输入包含三个整数 nn、mm 和 kk:分别表示节点数、边数和路径长度。节点编号为 1,2,…,n1,2,\dots,n。

随后有 mm 行描述边。每行包含三个整数 aa、bb 和 cc:表示存在一条从节点 aa 到节点 bb、权值为 cc 的边。

输出

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

数据范围

1≤n≤1001 \le n \le 100 1≤m≤n(n−1)1 \le m \le n(n-1) 1≤k≤1091 \le k \le 10^9 1≤a,b≤n1 \le a,b \le n 1≤c≤1091 \le c \le 10^9

样例输入

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

样例输出

27