题目描述

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

输入格式

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

输出格式

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

样例

4 5 
1 3 100 
3 2 50 
2 4 60 
1 2 40 
2 3 80

60 1 3