당신은 나쁜우유가 선적이 되어서 보내졌다는 것을 발견했다. 이 우유가 목적지 가게로 가는 길을 봉쇄하고자 하는데 , 목적지 가게로 가는 길은 여러가지가 있다.

길을 막는데는 특정한 양의 비용이 들고 목적지에 도착하지 못하도록 하는 가장 적은 양의 비용을 구하고 더불어 봉쇄하는 길의 집합을 구하고자 한다.

입력형식

첫번째 라인은 두 개의 정수 N , M 이 주어진다.

• N 은 2 이상 32 이하이고 이는 상점의 수
• M ( 0 <= M <= 1000) 은 길의 수 이다.

다음 줄 부터는 Si , Ei , Ci ( 1 <= Si,Ei <= N) 이다.

Si 에서 Ei 로 길이 있고 이 길을 막을 경우의 비용이다. ( 0 <= Ci <= 2,000,000 )

출력 형식

출력의 첫 라인은 두 개의 정수 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

출처: usaco