안정적인 네트워크

한 회사에는 본사 컴퓨터 1대와 여러 지사 컴퓨터가 있다. 본사 컴퓨터는 항상 1번이며, 모든 지사 컴퓨터와 직접 연결되어 있다. 또한 일부 지사 컴퓨터끼리도 서로 직접 연결되어 있다.

두 컴퓨터가 직접 연결되어 있지 않더라도 다른 컴퓨터들을 거쳐 통신할 수 있으면 서로 연결되어 있다고 본다.

회사는 장애가 발생해도 네트워크가 계속 연결되어 있기를 원한다. 직접 연결된 두 컴퓨터 사이의 연결 하나가 끊어져도 두 컴퓨터가 우회 경로로 연결되어 있어야 하고, 컴퓨터 하나가 고장 나도 고장 나지 않은 컴퓨터들끼리는 서로 연결되어 있어야 한다.

기존 지사 간 연결 상태와 새 연결 비용이 주어진다. 이미 안정적인 네트워크인지 판별하고, 안정적이지 않다면 최소 비용으로 지사 컴퓨터 사이의 연결을 추가하여 안정적인 네트워크를 만들어라.

첫째 줄에 두 정수 n과 m이 주어진다. n은 컴퓨터의 개수이고, m은 이미 직접 연결된 지사 컴퓨터 쌍의 개수이다. (1 <= n <= 1000, 0 <= m <= 10000)

다음 m개의 줄에는 서로 다른 두 지사 컴퓨터 x, y가 주어진다. 이는 x번 컴퓨터와 y번 컴퓨터가 직접 연결되어 있음을 뜻한다.

다음 n개의 줄에는 두 컴퓨터를 새로 연결할 때 드는 비용이 인접 행렬 형태로 주어진다. 서로 다른 두 컴퓨터를 연결하는 비용은 1 이상 30000 이하이고, i번 컴퓨터와 j번 컴퓨터를 연결하는 비용은 j번 컴퓨터와 i번 컴퓨터를 연결하는 비용과 같다. 본사 컴퓨터는 항상 1번이다.

첫째 줄에 필요한 최소 추가 비용 X와 추가할 연결의 개수 K를 출력한다.

다음 K개의 줄에는 새로 직접 연결할 두 지사 컴퓨터의 번호를 출력한다. 이미 안정적인 네트워크라면 X = 0, K = 0을 출력한다.

최소 비용을 만드는 방법이 여러 가지라면 그중 아무 방법이나 출력해도 된다.