선영이는 최근에 "노리스 타워" 라는 게임을 시작했다. 게임에는 아이템 종류가 총 n개가 있다. 이 아이템은 모두 선영이의 캐릭터가 착용할 수 있다. 아이템은 1번부터 n번까지 번호가 매겨져 있다. 선영이는 1번 아이템을 제작하려고 한다.

아이템을 얻는 방법은 다음과 같이 두 가지가 있다.

• 아이템을 구매할 수 있다. i번 아이템의 가격은 c_i원이다.
• 아이템을 제작할 수 있다. 총 m가지 제작방법이 있다. 서로 다른 두 종류의 아이템을 대장장이에게 갖다 주면, 대장장이는 무료로 결과 아이템을 전달해 준다.

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

입력 형식

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

둘째 줄에는 각 아이템의 가격 c_i가 아이템 번호가 증가하는 순서대로 주어진다. (0 ≤ c_i ≤ 10⁹)

다음 m개 줄에는 제작에 필요한 아이템과 그 결과 아이템의 번호 a_i, x_i, y_i가 주어진다. 대장장이에게 x_i번과 y_i번 아이템을 하나씩 가져다주면, a_i번 아이템을 결과로 준다는 뜻이다. (1 ≤ a_i, x_i, y_i ≤ n, a_i ≠ x_i, x_i ≠ y_i, y_i ≠ a_i)

출력 형식

각 테스트 케이스마다 1번 아이템을 얻는데 필요한 돈의 최솟값을 출력한다.

예제 입력

5 3
5 0 1 2 5
5 2 3
4 2 3
1 4 5

예제 출력

2