题目内容

四年校园时光即将结束，小明和室友计划一次难忘的毕业旅行。他们准备从 $A$ 城市出发，前往他们已经久仰的 $B$ 城市。两座城市之间有多种出行方案，既可直达，也可途经其他城市中转，每条路线的费用不相同。

请帮助他们在预算 $w$ 内，找到花费最少的路线。

输入描述

前有三个整数 $n,m,w$：

• $n$：城市数量（$2 \le n \le 100$）
• $m$：路线数量（$1 \le m \le 1000$）
• $w$：最大预算（$1 \le w \le 10^5$）

接下来是一个二维数组，记录了所有的路线信息。每条路线有 $3$ 个整数 $u,v,cost$：

• $u$：起点城市（$1 \le u \le n$）
• $v$：终点城市（$1 \le v \le n$）
• $cost$：所需费用（$1 \le cost \le 10^5$）

输出描述

• 若存在满足预算的最优路线，返回最小花费；
• 若不存在，则返回 $-1$。

补充说明

1. 出发城市编号为 $1$，目的地城市编号为 $n$ 所代表的值。
2. 每条路线的起点和终点都不相同（$u \ne v$），且只能单方向通行（$u \rightarrow v$，不能 $v \rightarrow u$）。
3. 从城市 $u$ 到城市 $v$，不存在多条不同费用的路线。

样例1

输入

3,3,10,[[1,2,5],[2,3,5],[1,3,8]]

输出

8

说明

解释：从城市 $1$ 到城市 $3$，直达花费 $8$。在预算内最优。

中转途经城市 $2$： $5+5=10$，费用更高。

样例2

输入

4,4,20,[[1,2,5],[2,3,5],[3,4,5],[1,4,25]]

输出

15

说明

解释：直达 $25$ 超出预算。

路径： $1 \rightarrow 2 \rightarrow 3 \rightarrow 4$ 花费 $15$。

为最小可行方案。

样例3

输入

3,3,5,[[1,2,3],[2,3,3],[1,3,10]]

输出

-1

说明

解释：所有可行路径都超过预算 $5$，返回 $-1$ 表示无解。