시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 256 MB 99 30 24 35.294%

문제

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

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

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

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

입력

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

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

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

출력

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

예제 입력

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

예제 출력

2

힌트