Minimum Cost Disruption in Milk Delivery Network

You have taken over the operations at Sanlu Milk Company on your first day, and disaster strikes: a batch of milk contaminated with melamine has been accidentally shipped out. Unfortunately, the contaminated milk has already entered a vast and complex delivery network consisting of warehouses and unidirectional trucks. Each truck transports milk in one fixed direction between two warehouses and has an associated economic cost if its route is stopped.

You know which retailer was going to receive this batch of milk. In order to prevent the contaminated milk from reaching the retailer, you must disable a subset of these trucks. Your goal is to decide which trucks to disable such that all possible delivery paths from the origin warehouse, where the contaminated milk lies, to the retailer are cut off, while minimizing the total economic loss.

Mathematically, you are given a directed graph \(G=(V,E)\) with \(n\) nodes (warehouses) and \(m\) edges (trucks). Each edge \(e=(u,v)\) has a cost \(c_e\) to disable it. Let \(s\) be the starting warehouse (the source of the contaminated milk) and \(t\) be the retailer's warehouse. The objective is to choose a set of edges \(E'\subseteq E\) with minimal total cost \(\sum_{e\in E'} c_e\) such that there is no path from \(s\) to \(t\) in the graph \(G\setminus E'\). By the max-flow min-cut theorem, this cost is equal to the maximum flow from \(s\) to \(t\), when the capacities of the edges are set to their disable costs.

Your task is to compute and output the minimum total cost needed to disrupt all possible delivery routes from \(s\) to \(t\).

inputFormat

The first line of input contains four integers \(n\), \(m\), \(s\), and \(t\) (1 \(\leq n \leq 10^5\), 1 \(\leq m \leq 10^5\)), where \(n\) is the number of warehouses, \(m\) is the number of trucks, \(s\) is the index of the source warehouse containing the contaminated milk, and \(t\) is the retailer's warehouse.

Each of the next \(m\) lines contains three integers \(u\), \(v\), and \(c\) (1 \(\leq u,v \leq n\), \(u \neq v\), 1 \(\leq c \leq 10^5\)), representing a directed truck route from warehouse \(u\) to warehouse \(v\) with a disable cost of \(c\).

outputFormat

Output a single integer representing the minimum total cost needed to disable enough trucks so that no path exists from warehouse \(s\) to warehouse \(t\).

sample

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

3