Jungol

N개의 도시들이 일방 통행 도로로 연결되어 있다.

도시들에 식량을 공급하기 위해 일부 도시에 식량 창고를 만들 것이다.

도시들마다 식량 창고를 만드는 비용은 각각 다르다.

A 번 도시에 만든 창고에서 B 번 도시에 식량을 공급하기 위해서는, A 에서 B 로 갔다가 다시 A 로 돌아오는 경로가 존재해야 한다.

도로 정보와 각 도시에 창고를 만드는 비용들이 입력될 때, 모든 도시에 식량을 공급하기 위한 최소 비용을 구하는 프로그램을 작성하자.

입력

첫 줄에는 도시 개수 N (1 이상 200 이하)가 주어진다.

둘째 줄에는 각 도시에 창고를 만드는 비용이 한 줄로 입력된다. (비용은 각각 100만 이하)

셋째 줄부터는 도로의 정보가 총 N 줄에 걸쳐 입력된다.

A 번째 줄의 B 번째 문자가 0 인 경우, A 번 도시에서 B 번 도시로 갈 수 없다는 것을 의미한다.

1 인 경우 A 번 도시에서 B 번 도시로 갈 수 있다.

출력

첫째 줄에 모든 도시에 식량을 공급하기 위한 최소 비용을 출력한다.

예제1

1, 5, 6번 도시에 식량 창고를 만드는 것이 최소다.

이 비용은 9 + 2 + 3 = 14 이다.

출처

@againalgo

식량 창고 2초 128MB