Economic Deployment for Road Monitoring

The Road Safety Department plans to deploy a monitoring system along the roads from city A to city B. The road network is given as an undirected graph \(G=(V,E)\) with nodes \(1,2,\dots,n\). City A is located at node \(s\) and city B at node \(t\). Each edge \(e\) has an installation cost \(W(e)\) if a monitoring device is installed on it.

When an emergency occurs, the department may assign manpower to some roads in order to guarantee that every path from \(s\) to \(t\) contains at least one road that is monitored (i.e. either a device is installed on that road or it is covered by manpower). The response difficulty is defined as the minimum number of roads that must be manned so that every \(s\)-\(t\) path has at least one monitored road.

Because installing devices on different roads may cost differently, the department wants to choose a deployment plan in which they install devices on a subset \(S\subseteq E\) such that the overall response difficulty (the minimum number of roads to be manned in the remaining network \(E\setminus S\)) does not exceed \(k\), while the total cost of installed devices is minimized.

Formally, let the remaining set of edges after device installation be \(F = E \setminus S\). Note that if we assign manpower to a set of roads in \(F\) such that every \(s\)-\(t\) path in \(F\) contains at least one manned road, then the minimum number of roads that must be manned is exactly the size of a minimum \(s\)-\(t\) cut in \(F\) (where each edge has unit capacity). The requirement is that the minimum cut in \(F\) is at most \(k\). Your task is to choose \(S\) (i.e. decide which roads to install a device on) so that the sum of \(W(e)\) for \(e\in S\) is minimized and the response difficulty is \(\le k\).

Note: If no road is left without a device (i.e. \(F\) is empty), then there is no \(s\)-\(t\) path and the response difficulty is considered 0.

---

Problem Input

The first line contains five integers \(n\), \(m\), \(k\), \(s\) and \(t\) where \(n\) is the number of nodes, \(m\) is the number of edges, \(k\) is the maximum allowed response difficulty, and \(s\) and \(t\) are the indices of the nodes where cities A and B are located respectively.

Then follow \(m\) lines, each containing three integers \(u\), \(v\) and \(w\) indicating that there is a bidirectional road between nodes \(u\) and \(v\) with device installation cost \(w\) (\(W(e)=w\)).

Problem Output

Output a single integer: the minimum total cost for installing devices such that the response difficulty does not exceed \(k\).

Explanation

One can view the problem dually. Let the total sum of installation costs of all edges be \(T = \sum_{e\in E}W(e)\). If one can find a partition of \(V\) into \(A\) and \(B\) with \(s\in A\) and \(t\in B\) such that the number of edges crossing the cut is \(\le k\) and the sum of costs of those crossing edges is \(f\), then one can install devices on the complement edges (with total cost \(T - f\)) and guarantee that the response difficulty does not exceed \(k\). The goal is to maximize \(f\) subject to the cut having at most \(k\) crossing edges, so that the installation cost, \(T-f\), is minimized.

inputFormat

The first line contains five integers \(n\), \(m\), \(k\), \(s\) and \(t\). Each of the following \(m\) lines contains three integers \(u\), \(v\) and \(w\) representing an undirected edge between nodes \(u\) and \(v\) with cost \(w\).

Sample Input:

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

outputFormat

Output a single integer representing the minimum total installation cost to ensure that the road network's response difficulty does not exceed \(k\).

Sample Output:

18

sample

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

18