시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 256 MB 131 41 33 41.250%

문제

선영이는 최근에 "노리스 타워" 라는 게임을 시작했다. 게임에는 아이템 종류가 총 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번 아이템을 얻는데 필요한 돈의 최솟값을 출력한다.

예제 입력 1

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

예제 출력 1

2
W3sicHJvYmxlbV9pZCI6Ijk0NDYiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM1NDRcdWM3NzRcdWQxNWMgXHVjODFjXHVjNzkxIiwiZGVzY3JpcHRpb24iOiI8cD5cdWMxMjBcdWM2MDFcdWM3NzRcdWIyOTQgXHVjZDVjXHVhZGZjXHVjNWQwICZxdW90O1x1YjE3OFx1YjlhY1x1YzJhNCBcdWQwYzBcdWM2Y2MmcXVvdDsgXHViNzdjXHViMjk0IFx1YWM4Y1x1Yzc4NFx1Yzc0NCBcdWMyZGNcdWM3OTFcdWQ1ODhcdWIyZTQuIFx1YWM4Y1x1Yzc4NFx1YzVkMFx1YjI5NCBcdWM1NDRcdWM3NzRcdWQxNWMgXHVjODg1XHViOTU4XHVhYzAwIFx1Y2QxZCBuXHVhYzFjXHVhYzAwIFx1Yzc4OFx1YjJlNC4gXHVjNzc0IFx1YzU0NFx1Yzc3NFx1ZDE1Y1x1Yzc0MCBcdWJhYThcdWI0NTAgXHVjMTIwXHVjNjAxXHVjNzc0XHVjNzU4IFx1Y2U5MFx1YjlhZFx1ZDEzMFx1YWMwMCBcdWNjMjlcdWM2YTlcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHVjNTQ0XHVjNzc0XHVkMTVjXHVjNzQwIDFcdWJjODhcdWJkODBcdWQxMzAgblx1YmM4OFx1YWU0Y1x1YzljMCBcdWJjODhcdWQ2MzhcdWFjMDAgXHViOWU0XHVhY2E4XHVjODM4IFx1Yzc4OFx1YjJlNC4gXHVjMTIwXHVjNjAxXHVjNzc0XHViMjk0IDFcdWJjODggXHVjNTQ0XHVjNzc0XHVkMTVjXHVjNzQ0IFx1YzgxY1x1Yzc5MVx1ZDU1OFx1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzU0NFx1Yzc3NFx1ZDE1Y1x1Yzc0NCBcdWM1YmJcdWIyOTQgXHViYzI5XHViYzk1XHVjNzQwIFx1YjJlNFx1Yzc0Y1x1YWNmYyBcdWFjMTlcdWM3NzQgXHViNDUwIFx1YWMwMFx1YzljMFx1YWMwMCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+XHVjNTQ0XHVjNzc0XHVkMTVjXHVjNzQ0IFx1YWQ2Y1x1YjllNFx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMmU0LiBpXHViYzg4IFx1YzU0NFx1Yzc3NFx1ZDE1Y1x1Yzc1OCBcdWFjMDBcdWFjYTlcdWM3NDAgY2lcdWM2ZDBcdWM3NzRcdWIyZTQuPFwvbGk+XHJcblx0PGxpPlx1YzU0NFx1Yzc3NFx1ZDE1Y1x1Yzc0NCBcdWM4MWNcdWM3OTFcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHVjZDFkIG1cdWFjMDBcdWM5YzAgXHVjODFjXHVjNzkxXHViYzI5XHViYzk1XHVjNzc0IFx1Yzc4OFx1YjJlNC4gXHVjMTFjXHViODVjIFx1YjJlNFx1Yjk3OCBcdWI0NTAgXHVjODg1XHViOTU4XHVjNzU4IFx1YzU0NFx1Yzc3NFx1ZDE1Y1x1Yzc0NCBcdWIzMDBcdWM3YTVcdWM3YTVcdWM3NzRcdWM1ZDBcdWFjOGMgXHVhYzE2XHViMmU0IFx1YzhmY1x1YmE3NCwgXHViMzAwXHVjN2E1XHVjN2E1XHVjNzc0XHViMjk0IFx1YmIzNFx1YjhjY1x1Yjg1YyBcdWFjYjBcdWFjZmMgXHVjNTQ0XHVjNzc0XHVkMTVjXHVjNzQ0IFx1YzgwNFx1YjJlY1x1ZDU3NCBcdWM5MDBcdWIyZTQuPFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+XHVjMTIwXHVjNjAxXHVjNzc0XHVhYzAwIDFcdWJjODggXHVjNTQ0XHVjNzc0XHVkMTVjXHVjNzQ0IFx1YzViYlx1YjI5NFx1YjM3MCBcdWQ1NDRcdWM2OTRcdWQ1NWMgXHViM2M4XHVjNzU4IFx1Y2Q1Y1x1YzE5Zlx1YWMxMlx1Yzc0NCBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVjNTQ0XHVjNzc0XHVkMTVjIFx1Yzg4NVx1Yjk1OFx1Yzc1OCBcdWMyMTggblx1YWNmYyBcdWM4MWNcdWM3OTEgXHViYzI5XHViYzk1XHVjNzU4IFx1YzIxOCBtXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDEgJmxlOyBuICZsZTsgMTAsMDAwLCAwICZsZTsgbSAmbGU7IDEwMCwwMDApPFwvcD5cclxuXHJcbjxwPlx1YjQ1OFx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVhYzAxIFx1YzU0NFx1Yzc3NFx1ZDE1Y1x1Yzc1OCBcdWFjMDBcdWFjYTkgY2lcdWFjMDAgXHVjNTQ0XHVjNzc0XHVkMTVjIFx1YmM4OFx1ZDYzOFx1YWMwMCBcdWM5OWRcdWFjMDBcdWQ1NThcdWIyOTQgXHVjMjFjXHVjMTFjXHViMzAwXHViODVjIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDAgJmxlOyBjPHN1Yj5pPFwvc3ViPiAmbGU7IDEwPHN1cD45PFwvc3VwPik8XC9wPlxyXG5cclxuPHA+XHViMmU0XHVjNzRjIG1cdWFjMWMgXHVjOTA0XHVjNWQwXHViMjk0IFx1YzgxY1x1Yzc5MVx1YzVkMCBcdWQ1NDRcdWM2OTRcdWQ1NWMgXHVjNTQ0XHVjNzc0XHVkMTVjXHVhY2ZjIFx1YWRmOCBcdWFjYjBcdWFjZmMgXHVjNTQ0XHVjNzc0XHVkMTVjXHVjNzU4IFx1YmM4OFx1ZDYzOCBhPHN1Yj5pPFwvc3ViPiwgeDxzdWI+aTxcL3N1Yj4sIHk8c3ViPmk8XC9zdWI+XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHViMzAwXHVjN2E1XHVjN2E1XHVjNzc0XHVjNWQwXHVhYzhjIHg8c3ViPmk8XC9zdWI+XHViYzg4XHVhY2ZjIHk8c3ViPmk8XC9zdWI+XHViYzg4IFx1YzU0NFx1Yzc3NFx1ZDE1Y1x1Yzc0NCBcdWQ1NThcdWIwOThcdWM1MjkgXHVhYzAwXHVjODM4XHViMmU0XHVjOGZjXHViYTc0LCBhPHN1Yj5pPFwvc3ViPlx1YmM4OCBcdWM1NDRcdWM3NzRcdWQxNWNcdWM3NDQgXHVhY2IwXHVhY2ZjXHViODVjIFx1YzkwMFx1YjJlNFx1YjI5NCBcdWI3M2JcdWM3NzRcdWIyZTQuICgxICZsZTsgYTxzdWI+aTxcL3N1Yj4sIHg8c3ViPmk8XC9zdWI+LCB5PHN1Yj5pPFwvc3ViPiAmbGU7IG4sIGE8c3ViPmk8XC9zdWI+ICZuZTsgeDxzdWI+aTxcL3N1Yj4sIHg8c3ViPmk8XC9zdWI+ICZuZTsgeTxzdWI+aTxcL3N1Yj4sIHk8c3ViPmk8XC9zdWI+ICZuZTsgYTxzdWI+aTxcL3N1Yj4pPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWI5YzhcdWIyZTQgMVx1YmM4OCBcdWM1NDRcdWM3NzRcdWQxNWNcdWM3NDQgXHVjNWJiXHViMjk0XHViMzcwIFx1ZDU0NFx1YzY5NFx1ZDU1YyBcdWIzYzhcdWM3NTggXHVjZDVjXHVjMTlmXHVhYzEyXHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiI5NDQ2IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiRHdhcmYgVG93ZXIiLCJkZXNjcmlwdGlvbiI6IjxwPkxpdHRsZSBWYXN5YSBpcyBwbGF5aW5nIGEgbmV3IGdhbWUgbmFtZWQgJmxkcXVvO0R3YXJmIFRvd2VyJnJkcXVvOy4gSW4gdGhpcyBnYW1lIHRoZXJlIGFyZSBuIGRpXHVmYjAwZXJlbnQgaXRlbXMsIHdoaWNoIHlvdSBjYW4gcHV0IG9uIHlvdXIgZHdhcmYgY2hhcmFjdGVyLiBJdGVtcyBhcmUgbnVtYmVyZWQgZnJvbSAxIHRvIG4uIFZhc3lhIHdhbnRzIHRvIGdldCB0aGUgaXRlbSB3aXRoIG51bWJlciAxLjxcL3A+XHJcblxyXG48cD5UaGVyZSBhcmUgdHdvIHdheXMgdG8gb2J0YWluIGFuIGl0ZW06PFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+WW91IGNhbiBidXkgYW4gaXRlbS4gVGhlIGktdGggaXRlbSBjb3N0cyBjaSBtb25leS48XC9saT5cclxuXHQ8bGk+WW91IGNhbiBjcmFmdCBhbiBpdGVtLiBUaGlzIGdhbWUgc3VwcG9ydHMgb25seSBtIHR5cGVzIG9mIGNyYWZ0aW5nLiBUbyBjcmFmdCBhbiBpdGVtLCB5b3UgZ2l2ZSB0d28gcGFydGljdWxhciBkaVx1ZmIwMGVyZW50IGl0ZW1zIGFuZCBnZXQgYW5vdGhlciBvbmUgYXMgYSByZXN1bHQuPFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+SGVscCBWYXN5YSB0byBzcGVuZCB0aGUgbGVhc3QgYW1vdW50IG9mIG1vbmV5IHRvIGdldCB0aGUgaXRlbSBudW1iZXIgMS48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBcdWZiMDFyc3QgbGluZSBvZiBpbnB1dCBjb250YWlucyB0d28gaW50ZWdlcnMgbiBhbmQgbSAoMSAmbGU7IG4gJmxlOyAxMCAwMDA7IDAgJmxlOyBtICZsZTsgMTAwIDAwMCkgJm1kYXNoOyB0aGUgbnVtYmVyIG9mIGRpXHVmYjAwZXJlbnQgaXRlbXMgYW5kIHRoZSBudW1iZXIgb2YgY3JhZnRpbmcgdHlwZXMuPFwvcD5cclxuXHJcbjxwPlRoZSBzZWNvbmQgbGluZSBjb250YWlucyBuIGludGVnZXJzIGM8c3ViPmk8XC9zdWI+ICZtZGFzaDsgdmFsdWVzIG9mIHRoZSBpdGVtcyAoMCAmbGU7IGM8c3ViPmk8XC9zdWI+ICZsZTsgMTA8c3VwPjk8XC9zdXA+KS48XC9wPlxyXG5cclxuPHA+VGhlIGZvbGxvd2luZyBtIGxpbmVzIGRlc2NyaWJlIGNyYWZ0aW5nIHR5cGVzLCBlYWNoIGxpbmUgY29udGFpbnMgdGhyZWUgZGlzdGluY3QgaW50ZWdlcnMgYTxzdWI+aTxcL3N1Yj4sIHg8c3ViPmk8XC9zdWI+LCB5PHN1Yj5pPFwvc3ViPiAmbWRhc2g7IGE8c3ViPmk8XC9zdWI+IGlzIHRoZSBpdGVtIHRoYXQgY2FuIGJlIGNyYWZ0ZWQgZnJvbSBpdGVtcyB4PHN1Yj5pPFwvc3ViPiBhbmQgeTxzdWI+aTxcL3N1Yj4gKDEgJmxlOyBhPHN1Yj5pPFwvc3ViPiwgeDxzdWI+aTxcL3N1Yj4sIHk8c3ViPmk8XC9zdWI+Jm5ic3A7JmxlOyBuLCBhPHN1Yj5pPFwvc3ViPiZuYnNwOyZuZTsgeDxzdWI+aTxcL3N1Yj4sIHg8c3ViPmk8XC9zdWI+Jm5ic3A7Jm5lOyB5PHN1Yj5pPFwvc3ViPiwgeTxzdWI+aTxcL3N1Yj4mbmJzcDsmbmU7IGE8c3ViPmk8XC9zdWI+KS48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5UaGUgb3V0cHV0IHNob3VsZCBjb250YWluIGEgc2luZ2xlIGludGVnZXIgJm1kYXNoOyB0aGUgbGVhc3QgYW1vdW50IG9mIG1vbmV5IHRvIHNwZW5kLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==