별자리 | cho.sh

우진이와 연두는 별자리를 좋아한다. 둘의 취향은 약간 다른데, 우진이는 직선을 좋아하고 연두는 원을 좋아한다. 준원이는 둘을 위해 별자리가 그려진 그림을 선물하려고 한다.

준원이는 먼저 종이 위에 $N$개의 별을 그렸다. 그 뒤 두 별을 잇는 $M$개의 간선을 그렸다. 준원이는 이제 마지막 작업으로 두께가 $K$ 이상인 모든 간선만을 강조할 예정이다. $K$는 간선의 두께 중에서 고른다.

준원이는 우진이와 연두 모두와 친하기 때문에 강조된 간선으로만 이루어진 그림에서 직선과 원의 개수 차이를 최소로 하려고 한다.

별자리의 별 개수를 $V$라 할 때 별의 번호를 $1$부터 $V$까지 적절히 재배열해 $i$번 별과 $i+1$번 별을 잇는 간선들만 존재한다면 그 별자리는 직선이라고 부른다. (단, $V \geq 2$, $1 \leq i \leq V-1$)
별자리의 별 개수를 $V$라 할 때 별의 번호를 $1$부터 $V$까지 적절히 재배열해 $1$번 별과 $V$번 별을 잇는 간선, $i$번 별과 $i+1$번 별을 잇는 간선들만 존재한다면 그 별자리는 원이라고 부른다. (단, $V \geq 3$, $1 \leq i \leq V-1$)
별자리란 별의 집합이며, 집합 내의 모든 쌍의 별이 간선으로 이루어진 경로로 연결되어 있고, 집합 밖의 별과 집합 내의 별이 연결되어 있지 않은 것이다.

직선의 개수와 원의 개수 차이를 최소로 하는 $K$가 여러 가지라면 준원이는 그중 가장 작은 값을 택할 것이다. 많은 간선이 강조된 그림일수록 아름답기 때문이다.

준원이가 택할 $K$의 값과 그때 직선과 원의 개수 차이를 구해주자.

첫 번째 줄에 별의 개수 $N$, 간선의 개수 $M$이 공백으로 구분되어 주어진다.

이후 $M$개의 줄에 걸쳐 간선들의 정보가 주어진다.

각 줄에는 세 개의 정수 $X$, $Y$, $W$가 공백으로 구분되어 주어지며, 이는 $X$번 별과 $Y$번 별을 연결하는 두께 $W$의 간선을 나타낸다.

준원이가 택할 $K$의 값과 그때 직선과 원의 개수 차이를 공백으로 구분하여 출력한다.