Ji Song 喜欢研究图论。 起初，他研究了最小生成树。 接着，他研究了最短路。 现在，他正在研究图的割问题。 给定一个有向带权图（不要求连通）以及源点和汇点。 显然，源点和汇点都是图中的节点。 你需要移除图中的一些边，使得在剩余的图中，从源点到汇点不存在路径。 此时，所有被移除边的权重之和称为“割”。 Ji Song 已经知道最小割等于原图中从源点到汇点的最大流。 现在他想知道该图的第 $K$ 小割。 他可以计算第 $K$ 小生成树和第 $K$ 短路，但他无法计算第 $K$ 小割。 请帮帮他。

输入格式

第一行包含 5 个整数 $N, M, K, S, T$。 $N$ ($1 \le N \le 100$) —— 表示图的节点数， $M$ ($1 \le M \le 1000$) —— 表示图的边数， $K$ ($1 \le K \le 100$)， $S$ ($0 \le S < N$) —— 表示源点的索引， $T$ ($0 \le T < N$) —— 表示汇点的索引 ($S \neq T$)。

接下来的 $M$ 行，每行包含三个整数 $a, b, c$ —— 表示一条连接 $a$ 和 $b$ 的边，其权重为 $c$ ($0 \le a, b < N, a \neq b$)。 为了简化问题，对于每个 $i$ ($0 \le i < N, i \neq S, i \neq T$)，至少存在一条连接 $i$ 和 $T$ 的边。

输出格式

输出问题的答案。 如果不存在第 $K$ 小割，输出 -1。

样例

样例输入 1

3 3 3 0 2
0 1 1
0 2 3
1 2 2

样例输出 1

6