본 문제에서는 다음과 같이 용어를 정의하고 있다고 생각합니다.

'안정적인 네트워크': 네트워크에 고장이 발생하더라도 고장나지 않은 컴퓨터들이 연결되어있는 상태.

'고장의 첫 번째 경우': 직접 연결되어 있는 두 컴퓨터의 연결이 끊어진 상태(두 컴퓨터 간의 간선이 존재하지 않는 경우). 이 경우, 안정적인 네트워크를 위해서는 두 컴퓨터를 제외한 다른 컴퓨터들을 경유하여 연결되어 있어야 함.

그런데 이 경우 아래의 케이스와 같이, 컴퓨터의 개수가 2대이며 추가적인 edge가 주어지지 않을 때는(즉, m = 0) 정답을 도출할 수 없게 됩니다. 이 경우 컴퓨터 1과 컴퓨터 2가 직접 연결되어 있는데, 만약 이 연결이 '고장의 첫 번째 경우'로 끊어지는 경우, 컴퓨터 1과 컴퓨터 2는 서로 도달할 수 없으므로 안정적인 네트워크가 아니지만 다른 컴퓨터가 존재하지 않으므로 경유를 통해 네트워크를 안정적으로 만들 수 없습니다.

현재는 본 케이스에 대한 예외 조건이 없으므로, 다음과 같은 조건을 추가해주시면 감사하겠습니다.

<현재 기술된 '입력'>

첫째 줄에 두 정수 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번 컴퓨터이다.

<수정을 거친 '입력'>

첫째 줄에 두 정수 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번 컴퓨터이다. 안정적인 네트워크를 만들 수 없는 경우는 주어지지 않는다.