10442 - 追查坏牛奶

你第一天接手光明牛奶公司就发生了一件倒霉的事情：公司不小心发送了一批坏牛奶。很不幸，你发现这件事的时候，坏牛奶已经进入了送货网。这个送货网很大， 而且关系复杂。你知道这批牛奶要发给哪个零售商，但是要把这批牛奶送到他手中有许多种途径。送货网由一些仓库和运输卡车组成，每辆卡车都在各自固定的两个 仓库之间单向运输牛奶。在追查这些坏牛奶的时候，有必要保证它不被送到零售商手里，所以必须使某些运输卡车停止运输，但是停止每辆卡车都会有一定的经济损 失。你的任务是，再保证坏牛奶不送到零售商的前提下，制定出停止卡车运输的方案，使损失最小。

第一行: 两个整数M(0<=M<=1000)、N(2<=N<=32), N表示仓库的数目，M表示运输卡车的数量。仓库1代 表发货工厂，仓库N代表坏牛奶要发往的零售商。 第2..M+1行: 每行3个整数 Si, Ei, Ci. Si ,Ei表示这 辆卡车的出发仓库，目的仓库。Ci(0 <= C i <= 2,000,000) 表示让这辆卡车停止运输的损失

第1行两个整数c、t,c表示最小的损失，T表示要停止的最少卡车数。接下来t 行表示你要停止哪几条线路。如果有多种方案使损失最小，输出停止的线路最少的方案。

Pollutant Control Hal Burch It's your first day in Quality Control at Merry Milk Makers, and already there's been a catastrophe. You've discovered that a shipment of bad milk has been sent out. Unfortunately, you didn't discover this until the milk was already into your delivery system, a rather large and complex affair. You do, however, know which grocer that milk was destined for, but there may be multiple ways for the milk to get to that store.

The delivery system is made up of a several warehouses, with trucks running from warehouse to warehouse moving milk. While the milk will be found quickly, it is important that it does not make it to the grocer, so you must shut down enough trucks to ensure that it is impossible for the milk to get to the grocer in question. Every route costs a certain amount to shut down. Find the minimum amount that must be spent to ensure the milk does not reach its destination, along with a set of trucks to shut down that achieves this goal at that cost.

PROGRAM NAME: milk6 INPUT FORMAT Line 1: Two space separated integers, N and M. N (2 <= N <= 32) is the number of warehouses that Merry Milk Makers has, and M (0 <= M <= 1000) is the number of trucks routes run. Warehouse 1 is actually the productional facility, while warehouse N is the grocer to which which the bad milk was destined.
Line 2..M+1: Truck routes: three space-separated integers, Si, Ei, and Ci. Si and Ei (1 <= Si,Ei <= N) correspond to the pickup warehouse and dropoff warehouse for the truck route. Ci (0 <= Ci <= 2,000,000) is the cost of shutting down the truck route.

SAMPLE INPUT (file milk6.in) 4 5 1 3 100 3 2 50 2 4 60 1 2 40 2 3 80

OUTPUT FORMAT The first line of the output should be two integers, C and T. C is the minimum amount which must be spent in order to ensure the our milk never reaches its destination. T is the minimum number of truck routes that you plan to shut down in order to achive this goal. The next T lines sould contain a sorted list of the indexes of the truck routes that you suggest shutting down. If there are multiple sets of truck routes that achieve the goal at minimum cost, choose one that shuts down the minimum number of routes. If there are still multiple sets, choose the one whose initial routes have the smallest index.

SAMPLE OUTPUT (file milk6.out) 60 1 3