图上最短路IV

题目描述

给定一张 $n$ 点 $m$ 条边构成的带权有向图，并且给定起点 $S$ 以及终点 $T$，请求出 $S$ 到 $T$ 的经过不超过 $k$ 条边的最短路径的长度，如果 $S$ 和 $T$ 之间不可达，则输出unreachable。

注意，这里指的不超过 $k$ 条边指的并非是边的种类，而是经过边的数量，经过同一条边若干次也会被计算在边的限制之中。

输入格式

第一行为5个整数 $n,m,S,T, k$，分别表示点数，边数，起点和终点以及边数限制。 接下来 $m$ 行，每行包含三个整数 $u,v,w$，表示节点 $u$ 和节点 $v$ 之间存在一条从 $u \rightarrow v$ 且长度为 $w$ 的边。

数据保证给定的图中可能存在负权回路。

数据范围: $1 \le n,k \le 500$ $1 \le m \le 20000$ $1 \le S, T, u, v \le n$ $-10^9 \le w \le 10^9$

输出格式

一个整数，表示答案。

样例 #1

样例输入 #1

6 9 1 6 3
1 2 1
1 3 2
2 4 -3
3 5 3
3 4 1
5 6 1
4 6 3
3 2 2
5 4 1

样例输出 #1

1

提示

一条可能的最短路。