P1344 {{[USACO4.4] Pollutant Control}}

{{}}

{{On your first day at Sanlu Milk Company, something unlucky happens: the company accidentally shipped a batch of milk containing melamine. Unfortunately, by the time you discovered this, the melamine-tainted milk had already entered the delivery network. The network is large and complex. You know which retailer this batch is destined for, but there are many different routes to deliver it. The delivery network consists of warehouses and transport trucks. Each truck carries milk in one direction between a fixed pair of warehouses. To trace and block the tainted milk, you must ensure it is not delivered to the retailer, so some transport trucks must be stopped. However, stopping each truck incurs a certain monetary loss. Your task is to decide which trucks to stop so that the tainted milk cannot reach the retailer, while minimizing the total loss.}}

{{The first line contains two integers $N$ and $M$. $N$ is the number of warehouses, and $M$ is the number of transport trucks. Warehouse $1$ is the factory (source), and warehouse $N$ is the retailer that the melamine-tainted milk is destined for. Lines $2\sim M+1$ each contain three integers $S_i$, $E_i$, and $C_i$. Here, $S_i$ and $E_i$ are the starting and ending warehouse of this truck, respectively. $C_i$ is the loss incurred by stopping this truck.}}

{{Output two integers $C$ and $T$. $C$ is the minimum total loss, and, among all solutions with minimum loss, $T$ is the minimum number of trucks that must be stopped.}}

{{Constraints: For $100 \%$ of the testdata, $2 \le N \le 32$, $0 \le M \le 10^3$, $1 \le S_i \le N$, $1 \le E_i \le N$, $0 \le C_i \le 2 \times 10^6$. Translation of the problem statement is from NOCOW. USACO Training Section 4.4.}} Translated by ChatGPT 5