2406번 - 안정적인 네트워크 스페셜 저지

한 회사는 본사와 지사의 컴퓨터들을 연결하는 네트워크 시설을 보유하고 있다. 각 지사에는 네트워크용 컴퓨터가 한 대씩 있으며, 이들은 본사의 메인 컴퓨터와 직접 연결되어 있다. 몇몇 지사들끼리 연결되어 있는 경우도 있다.

네트워크 시설에서는 두 컴퓨터가 직접 연결되어 있지 않더라도 다른 컴퓨터들을 경유하여 연결될 수 있다. 예를 들어 1, 2번 컴퓨터가 직접 연결되어 있고, 1, 3번 컴퓨터가 직접 연결되어 있다면, 이것은 2, 3번 컴퓨터가 연결되어 있는 효과도 발휘한다는 것이다.

회사 측에서는 네트워크에 고장이 발생하더라도 컴퓨터들이 연결되어 있도록 안정적인 네트워크를 구축하고자 한다. 네트워크에 고장이 발생하는 경우는 두 가지가 있다. 첫 번째는 직접 연결되어 있는 두 컴퓨터의 연결이 끊어지는 경우이다. 회사 측은 이런 경우에도 이 두 컴퓨터가 다른 컴퓨터들을 경유하여 연결되어 있기를 원한다. 두 번째는 컴퓨터가 고장 나는 경우이다. 회사 측은 이런 경우에는 고장 나지 않은 컴퓨터들끼리 연결되어 있기를 원한다.

예제로 주어진 입력에서 1, 2번 컴퓨터의 연결이 끊어지더라도, 이 두 컴퓨터는 3번 컴퓨터를 통해서 연결되게 된다. 하지만 1번 컴퓨터가 고장 나는 경우에는 5번 컴퓨터가 다른 컴퓨터들과 연결되어 있지 못하게 된다. 따라서 5번 컴퓨터를 다른 컴퓨터와 직접 연결해 주어야 한다.

두 컴퓨터를 연결하는 데 소요되는 비용은 일정하지 않다. 당신은 네트워크의 연결 상태를 입력받아 이 네트워크가 안정적인 네트워크인지 판별하고, 만약 아닐 경우에는 최소 비용으로 회사의 네트워크가 안정적이 되도록 하여야 한다.

첫째 줄에 두 정수 n(1 ≤ n ≤ 1,000), m(0 ≤ m ≤ 10,000)이 주어진다. n은 컴퓨터의 개수이며, m은 연결되어 있는 지사 컴퓨터들의 쌍의 개수이다. 다음 m개의 줄에는 두 정수 x, y가 주어진다. 이는 서로 다른 두 컴퓨터, x번 컴퓨터와 y번 컴퓨터가 직접 연결되어 있음을 의미한다. 다음 n개의 줄에는 인접 행렬의 형태로 두 컴퓨터를 연결할 때 드는 비용이 주어진다. 이 값은 1 이상 30,000이하의 정수이며, i번 컴퓨터와 j번 컴퓨터를 연결할 때 드는 비용은 j번 컴퓨터와 i번 컴퓨터를 연결할 때 드는 비용과 같다. 본사의 컴퓨터는 항상 1번 컴퓨터이다.

첫째 줄에 최소 비용 X와 연결할 컴퓨터들의 쌍의 개수 K를 출력한다. 다음 K개의 줄에는 두 정수로 연결할 컴퓨터들의 번호를 출력한다. 만약 주어진 입력이 안정적인 네트워크라면 X=0이고 K=0이 된다.