Description

Given a directed weighted network $G = (V, E)$, a weight function $w: E \rightarrow \mathbb{Z^{*}}$ (i.e., for any edge $e$, the weight $w(e)$ is a positive integer), and vertices $s, t \in V$. Consider any edge set $S \subseteq E$, and let $G' = (V, E - S)$. If there is no path from $s$ to $t$ in $G'$, then $S$ is valid.

Let $\mathfrak{S}$ be the set of all such edge sets $S$. Output the sums of edge weights of the smallest $k$ sets in $\mathfrak{S}$ by nondecreasing $w(S)$, where $w(S) = \sum_{e \in S} w(e)$.

Input Format

The first line contains $5$ positive integers $n, m, s, t, k$, where $s, t, k$ are as above, and $n, m$ denote $\lvert V \rvert, \lvert E \rvert$ (the numbers of vertices and edges). Vertices are labeled from $1$ to $n$. It is guaranteed that $s \neq t$.

The next $m$ lines each contain $3$ integers $x, y, z$, representing a directed edge from $x$ to $y$ with weight $z$. Multiple edges may exist, but there are no self-loops.

Output Format

If $\lvert \mathfrak{S} \rvert < k$, first output $\lvert \mathfrak{S} \rvert$ lines, each containing one integer, which are the first $\lvert \mathfrak{S} \rvert$ values of $w(S)$. Then output one more line with a single integer $-1$.

If $\lvert \mathfrak{S} \rvert \geq k$, output $k$ lines, which are the first $k$ values of $w(S)$.

In both cases, the outputs must be in nondecreasing order of $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

Hint

Translated by ChatGPT 5