아이템 제작

선영이는 최근에 "노리스 타워"라는 게임을 시작했다. 이 게임에는 아이템이 $n$종류 있고, 모두 선영이의 캐릭터가 착용할 수 있다. 아이템에는 1번부터 $n$번까지 번호가 붙어 있다. 선영이는 1번 아이템을 얻으려고 한다.

아이템을 얻는 방법은 두 가지다.

• 아이템을 구매할 수 있다. $i$번 아이템의 가격은 $c_i$원이다.
• 아이템을 제작할 수 있다. 제작 방법은 총 $m$가지다. 서로 다른 두 종류의 아이템을 대장장이에게 갖다 주면, 대장장이가 결과 아이템을 무료로 만들어 준다. 갖다 준 아이템 두 개는 돌려받지 못하므로, 같은 종류를 두 번 쓰려면 두 개를 따로 마련해야 한다.

선영이가 1번 아이템을 얻는 데 필요한 돈의 최솟값을 구하는 프로그램을 작성하시오.

첫째 줄에 아이템 종류의 수 $n$과 제작 방법의 수 $m$이 주어진다. ($1 \le n \le 10\,000$, $0 \le m \le 100\,000$)

둘째 줄에 아이템의 가격 $c_1, c_2, \dots, c_n$이 아이템 번호가 증가하는 순서대로 주어진다. ($0 \le c_i \le 10^9$)

다음 $m$개 줄에 제작 방법이 한 줄에 하나씩, 결과 아이템과 재료 아이템의 번호 $a_i$, $x_i$, $y_i$ 순으로 주어진다. 대장장이에게 $x_i$번과 $y_i$번 아이템을 하나씩 갖다 주면 $a_i$번 아이템을 결과로 준다는 뜻이다. ($1 \le a_i, x_i, y_i \le n$, $a_i \ne x_i$, $x_i \ne y_i$, $y_i \ne a_i$)

1번 아이템을 얻는 데 필요한 돈의 최솟값을 한 줄에 출력한다.