문제
구름이가 살고 있는 도시는 개의 지구와 각 지구를 잇는 개의 양방향 도로로 이루어진 도로망을 가지고 있다.
이 도시에서는 재개발을 통해 오래된 도시 구조에서 오는 문제를 타파하고자 하고 있다. 구름이가 살고 있는 도시의 각 지구는 주택 지구 혹은 산업 지구로 나뉘는데, 이름 그대로 주택 지구에는 사람들이 살고 산업 지구에는 일터가 있어서 사람들은 보통 주택 지구에서 산업 지구로 출퇴근을 한다.
현대모비스에 입사한 구름이는 자율 주행 및 네비게이션 기능을 적절히 갱신하기 위해서, 도시에서 이뤄지는 재개발이 어떻게 진행될 지를 알고 싶다. 구름이는 현재 도시의 재개발이 다음과 같은 과정을 통해 이루어질 예정인 것은 알고 있다.
예를 들어, 현재 도시가 위와 같은 도로망 구조를 가지고 있다고 가정해보자. 각 도로에 붙은 숫자는 맨 첫번째부터 순서대로 (주택 지구끼리 연결할 때 비용, 주택 지구와 산업 지구를 연결할 때 비용, 산업 지구끼리 연결할 때 비용)에 해당한다.
이 때, 번 지구와 번 지구를 주택 지구로, 번 지구와 번 지구를 산업 지구로 설정하는 경우, 각 도로를 재개발하는데 드는 비용은 다음과 같다.
따라서, 총 의 비용이 필요하고 이 경우가 최소이다.
구름이를 도와 위의 조건에 따라 재개발이 이루어질 때 필요한 최소 비용이 얼마인지 구하는 프로그램을 작성해보자.
입력 형식
첫째 줄에 도시를 구성하는 지구의 수 과 각 지구를 잇는 양방향 도로의 개수 이 주어진다()
둘째 줄부터 줄에 걸쳐 각 도시를 연결하는 번째 도로의 정보를 나타내는 다섯 개의 정수 가 주어진다(). 이는 번 도로가 번 지구와 번 지구를 연결하며, 주택지구끼리 연결할 경우의 비용은 , 주택지구와 산업지구를 연결할 경우의 비용은 , 산업지구끼리 연결할 경우의 비용은 라는 뜻이다(). 연결하는 지구 쌍이 동일한 도로는 최대 하나만 주어진다.
출력 형식
문제에 주어진 조건에 따라 도시를 재개발할 때 필요한 최소 비용을 첫째 줄에 출력한다.
* 문제에 대한 힌트는 블로그에서 확인할 수 있습니다.
* 문제에 대한 질문은 Q&A에 남겨주세요!