题目描述

一个工程用有向无环图表示。顶点表示事件，有向边表示活动，边权是活动所需的时间。一个事件必须等所有指向它的活动结束后才能发生。不同活动可以同时进行。

编号 $1$ 的事件是唯一的开始事件，编号 $n$ 的事件是唯一的结束事件。求完成整个工程的最短时间，并找出所有关键活动。关键活动是指：在其他活动时间不变的情况下，只要延长它的用时，就会使整个工程的最短完成时间增加。

输入格式

第一行两个整数 $n,m$。接下来 $m$ 行，每行三个整数 $u,v,w$，表示一项从事件 $u$ 到事件 $v$、用时为 $w$ 的活动。活动按输入顺序编号为 $1$ 至 $m$。

输出格式

第一行输出最短完成时间。第二行输出关键活动数量。第三行按编号递增输出所有关键活动编号。

样例

8 12
1 2 6
1 3 7
2 4 3
2 5 5
3 5 4
4 6 2
4 8 5
5 4 3
5 6 4
5 7 3
6 8 2
7 8 4

19
6
1 2 4 5 7 8

数据范围

$2\le n\le1000$，$n-1\le m\le10000$，$1\le w\le10^6$。保证没有自环或重边，图无环，事件 $1$ 是唯一入度为零的点，事件 $n$ 是唯一出度为零的点。