문제
성재와 민혁이가 달리기 시합을 한다.
먼저 시합의 주선자인 서연이가 N개의 지역 중 몇 곳의 지역을 골라서
원형(출발 지점과 도착 지점이 같은) 트랙을 정한 후 둘이서 한 바퀴 돈다.
서연이는 둘의 기록을 재고 승자를 결정한다. (당연히 완주시간이 짧은 쪽이 승자가 된다)
민혁이가 성재를 항상 이겨왔던 것을 지겨워하는 서연이는 성재가 완승하는 트랙을 만들고 싶어한다.
한편, 서연이는 성재와 민혁이의 달리기 기록을 알고 있는 길을 M개 알고 있다.
민혁이가 이길 가능성을 아예 없애기 위해선 M개의 길들만으로 트랙을 만들어야 한다.
한편, 경유 지역이 너무 많으면 주선자인 자신이 헷갈리기 때문에 경유 지역의 수는 최소화해야 한다.
서연이를 도와 성재가 완승하는 트랙을 구하는 프로그램을 작성하여라.
[서브태스크]
서브태스크 1 : N ≤ 11
서브태스크 2 : N ≤ 22
서브태스크 3 : N ≤ 111
서브태스크 4 : N ≤ 222
서브태스크 5 : 추가 제약 없음
입력
첫 번째 줄에는 지역의 수 N과 길의 수 M이 주어진다. (2 ≤ N ≤ 300, 2 ≤ M ≤ N(N-1))
두 번째 줄부터 M개의 줄에는 길의 시작점과 끝점 Sk, Ek (1 ≤ Sk, Ek ≤ N, Sk ≠ Ek)와 성재와 민혁이의 기록(초)이 주어진다.
기록은 106 이하이다.
출력
성재가 이기는 트랙 중 경유 지역의 수의 최솟값과,
그때 성재가 민혁이에 비해 앞설 수 있는 시간차의 최댓값을 출력한다.
단, 성재가 이기는 트랙은 항상 존재한다.
예제1
입력
34
1230
2330
310100
2104
출력
21 예제2
입력
57
1241
2351
3116
13155
2475
4514
5310
출력
52 힌트
출처
COCI 2013/2014 Contest 4