K Smallest s-t Cuts

Given a directed weighted graph \(G=(V,E)\) with a weight function \(w:E\to\mathbb{Z}^+\) (i.e. every edge has a positive integer weight), and two distinct vertices \(s\) and \(t\) in \(V\), consider an edge subset \(S\) such that when these edges are removed from \(G\) the resulting graph \(G'=(V, E\setminus S)\) contains no path from \(s\) to \(t\). Let \(\mathfrak{S}\) be the collection of all such edge subsets. For any \(S\in\mathfrak{S}\), define its weight as

[ w(S)=\sum_{e\in S}w(e). ]

Notice that for any valid \(S\) one may always take the induced cut determined by the vertex set reachable from \(s\) after the removal. In other words, if you let \(A\) be the set of vertices reachable from \(s\) in \(G-S\), then \(S\) must include all edges from \(A\) to \(V\setminus A\). It turns out that the minimum weight of any valid \(S\) is exactly the weight of such an induced cut.

Your task is: Given \(G=(V,E)\), two vertices \(s,t\), and an integer \(k\), enumerate all possible induced cuts defined by a vertex partition \(A\) with \(s\in A\) and \(t\notin A\), compute the cut weight \(w(A)=\sum_{\substack{u\in A,\ v\notin A\\ (u,v)\in E}}w(u,v)\) for each partition and then output the smallest \(k\) cut weights (in increasing order).

Note: Since any edge subset \(S\) that disconnects \(s\) and \(t\) necessarily contains the induced cut from the reachable set, it suffices to consider these induced cuts.

inputFormat

The first line contains five integers \(n\), \(m\), \(k\), \(s\) and \(t\), where \(n\) is the number of vertices, \(m\) is the number of edges, \(k\) is the number of minimum cuts to output, and \(s\) and \(t\) are the source and target vertices respectively. The vertices are numbered from 1 to \(n\).

Each of the following \(m\) lines contains three integers \(u\), \(v\) and \(w\), representing a directed edge from node \(u\) to node \(v\) with weight \(w\) (\(w>0\)).

Constraints: You can assume that \(n\) is small (e.g. \(n\leq 16\)) so that a brute-force enumeration over the subsets of vertices (excluding \(s\) and \(t\)) is feasible.

outputFormat

Output exactly \(k\) lines. The \(i\)th line contains a single integer representing the \(i\)th smallest cut weight among all induced cuts (i.e. vertex subsets \(A\) with \(s\in A\) and \(t\notin A\)). If there are fewer than \(k\) possible cuts, output the available ones only.

sample

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

2
3
4