1144번 - 싼 비용

1*1크기의 정사각형으로 나누어진 N*M크기의 직사각형 종이가 있다. 각 칸에는 정수가 하나씩 쓰여져 있다. 이 숫자를 비용이라고 하자.

이때, 가장 싼 연결된 칸의 집합을 찾는 프로그램을 작성하시오. 연결된 칸의 집합의 비용은 각 칸에 쓰여 있는 비용의 합이다.

칸이 연결되어 있다는 말은 그 집합의 한 칸에서 다른 칸으로 집합에 포함된 인접한 칸을 통해서 모두 이동할 수 있다는 의미이고, 두 칸이 인접해 있다는 소리는, 같은 변을 공유할 때이다. 크기가 0인 집합도 올바른 집합이다.

첫째 줄에 N과 M이 주어진다. N과 M은 9보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 숫자가 M개씩 주어진다. 각 숫자는 절댓값이 1000보다 작거나 같은 정수이다.

첫째 줄에 가장 싼 연결된 칸의 집합의 비용을 출력한다.