문제

구름이가 살고 있는 도시는 개의 지구와 각 지구를 잇는 개의 양방향 도로로 이루어진 도로망을 가지고 있다.

이 도시에서는 재개발을 통해 오래된 도시 구조에서 오는 문제를 타파하고자 하고 있다. 구름이가 살고 있는 도시의 각 지구는 주택 지구 혹은 산업 지구로 나뉘는데, 이름 그대로 주택 지구에는 사람들이 살고 산업 지구에는 일터가 있어서 사람들은 보통 주택 지구에서 산업 지구로 출퇴근을 한다.

현대모비스에 입사한 구름이는 자율 주행 및 네비게이션 기능을 적절히 갱신하기 위해서, 도시에서 이뤄지는 재개발이 어떻게 진행될 지를 알고 싶다. 구름이는 현재 도시의 재개발이 다음과 같은 과정을 통해 이루어질 예정인 것은 알고 있다.

1. 번 지구는 주택 지구, 번 지구는 산업 지구이다.
2. 도시의 각 도로도 모두 재개발이 이루어질 예정인데, 주택 지구끼리 연결하는 도로일 때,  주택 지구와 산업지구를 연결하는 도로일 때, 산업 지구끼리 연결하는 도로일 때 각각 재개발에 필요한 비용이 다르다. 이때, 주택 지구와 산업 지구를 오가는 통행량이 가장 많기 때문에 이 경우에 드는 재개발 비용이 가장 크다.
3. 번 지구부터 번 지구까지 각각의 지구는 주택 지구 혹은 산업 지구 둘 중 하나가 될 수 있다. 이 때 각 지구를 잇는 도로를 재개발하는데 드는 비용이 최소가 되도록 설정하려고 한다.

예를 들어,  현재 도시가 위와 같은 도로망 구조를 가지고 있다고 가정해보자. 각 도로에 붙은 숫자는 맨 첫번째부터 순서대로 (주택 지구끼리 연결할 때 비용, 주택 지구와 산업 지구를 연결할 때 비용, 산업 지구끼리 연결할 때 비용)에 해당한다.

이 때, 번 지구와 번 지구를 주택 지구로, 번 지구와 번 지구를 산업 지구로 설정하는 경우, 각 도로를 재개발하는데 드는 비용은 다음과 같다.

• 번 지구와 번 지구를 잇는 도로: 주택지구와 산업지구를 연결하므로, 의 비용이 필요
• 번 지구와 번 지구를 잇는 도로: 주택지구끼리 연결하므로, 의 비용이 필요
• 번 지구와 번 지구를 잇는 도로: 주택지구와 산업지구를 연결하므로, 의 비용이 필요
• 번 지구와 번 지구를 잇는 도로: 산업지구끼리 연결하므로, 의 비용이 필요

따라서, 총 의 비용이 필요하고 이 경우가 최소이다.

구름이를 도와 위의 조건에 따라 재개발이 이루어질 때 필요한 최소 비용이 얼마인지 구하는 프로그램을 작성해보자.

입력 형식

첫째 줄에 도시를 구성하는 지구의 수 과 각 지구를 잇는 양방향 도로의 개수 이 주어진다()

둘째 줄부터 줄에 걸쳐 각 도시를 연결하는 번째 도로의 정보를 나타내는 다섯 개의 정수 가 주어진다(). 이는 번 도로가 번 지구와 번 지구를 연결하며, 주택지구끼리 연결할 경우의 비용은 , 주택지구와 산업지구를 연결할 경우의 비용은 , 산업지구끼리 연결할 경우의 비용은 라는 뜻이다(). 연결하는 지구 쌍이 동일한 도로는 최대 하나만 주어진다.

출력 형식

문제에 주어진 조건에 따라 도시를 재개발할 때 필요한 최소 비용을 첫째 줄에 출력한다.

구름 블로그 방문하기

* 문제에 대한 힌트는 블로그에서 확인할 수 있습니다.

* 문제에 대한 질문은 Q&A에 남겨주세요!