题目描述

给出一个有向带全网络 $G=(V,E)$，权值函数 $w$：$E\to\mathbb{Z^*}$（即任意边 $e$ 的权值 $w(e)$ 均为正整数），和点 $x,t \in E$，使得在 $G'=(V,E-S)$ 上不存在 $s$ 到 $t$ 的路径。

设 $\mathfrak{S}$ 是所有满足条件的边集 $S$ 的全集，按 $w(S)$ 从小到大输出 $\mathfrak{S}$ 中前 $k$ 小的边集的边权和。其中 $w(S)=\sum\limits_{ e\in S}w(e)$。

输入格式

第一行包含 $5$ 个正整数 $n,m,s,t,k$，其中 $s,t,k$ 的意义如上，$n,m$ 分别表示 $\left|V\right|$，$\left|E\right|$（即点数和边数）。规定图中的结点用 $1$ 到 $n$ 的整数表示。保证 $s\neq t$。

接下来 $m$ 行，每行 $3$ 个整数 $x,y,z$，表示一条边权为 $z$ 的从 $x$ 到 $y$ 的边。

可能有重边，但保证没有自环。

输出格式

如果 $\left|\mathfrak{S}\right|<k$，先输出 $\left|\mathfrak{S}\right|$ 行，每行包含一个整数，表示前 $\left|\mathfrak{S}\right|$ 个$w(S)$，再输出一行一个整数 $-1$。

如果 $\left|\mathfrak{S}\right|\ge k$，则输出 $k$ 行，表示前 $k$ 个 $w(S)$。

两种情况均需按照 $w(S)$ 从小到大输出。

3 3 1 3 100
1 2 3
2 3 4
1 3 5

8
9
12
-1

5 8 1 5 10
1 2 45176
1 3 41088
1 4 32001
2 5 48931
3 5 39291
4 5 28970
2 3 48131
4 2 49795

116468
117192
118265
120223
145438
147235
149193
157556
158280
161311

数据规模与约定

对于 $30\%$ 的数据，$n\le 50$，$m\le 100$，$k\le 5\times 10^5$。边权不超过 $65536$。

对于另外 $40\%$ 的数据，$n\le 1.5\times 10^5$，$m\le 2n-4$，$k\le 5\times 10^5$。$s$ 有边连向所有非 $t$ 结点，所有非 $s$ 结点有边连向 $t$。边权不超过 $2^{31}-1$。

对于另外 $30$ 的数据，$n\le50$，$m\le1.5\times 10^3$，$k\le100$，边权不超过 $65536$。