주유소

어떤 나라에 $N$개의 도시가 있고, 각 도시에는 1번부터 $N$번까지 번호가 붙어 있다. 서로 다른 두 도시를 양방향으로 직접 잇는 도로가 $M$개 있으며, 도로마다 길이가 다를 수 있다. 길이의 단위는 km다.

1번 도시에서 $N$번 도시까지 자동차로 이동하려고 한다. 출발할 때 자동차에 기름이 없으므로 주유소에서 기름을 넣고 출발해야 한다. 기름통의 크기는 무제한이라 한 번에 얼마든지 많이 넣을 수 있다. 도로를 1km 달릴 때마다 기름 1리터를 쓴다. 도시마다 주유소가 하나씩 있고, 리터당 가격은 도시마다 다를 수 있다. 가격의 단위는 원이다. 이미 지나온 도시를 다시 지나가도 되고, 지날 때마다 그 도시의 주유소에서 기름을 더 넣어도 된다.

아래 그림은 도시가 4개, 도로가 4개인 예다. 원 안의 숫자는 도시 번호, 원 옆의 숫자는 그 도시 주유소의 리터당 가격, 도로 옆의 숫자는 도로의 길이다. 리터당 가격은 1번 도시부터 차례로 5원, 2원, 4원, 1원이고, 도로는 1번과 3번을 잇는 길이 3인 도로, 1번과 2번을 잇는 길이 2인 도로, 3번과 4번을 잇는 길이 4인 도로, 2번과 4번을 잇는 길이 15인 도로다.

1번 도시에서 7리터를 넣고 3번 도시를 거쳐 4번 도시까지 가면 비용은 $7 \times 5 = 35$원이다. 1번 도시에서 3리터를 넣어($3 \times 5 = 15$원) 3번 도시까지 간 다음, 3번 도시에서 4리터를 넣어($4 \times 4 = 16$원) 4번 도시에 도착하면 비용은 31원이다. 1번 도시에서 2리터를 넣어($2 \times 5 = 10$원) 2번 도시로 가고, 2번 도시에서 9리터를 넣어($9 \times 2 = 18$원) 1번과 3번 도시를 거쳐 4번 도시에 도착하면 비용은 28원이다.

각 도시 주유소의 리터당 가격과 각 도로의 길이가 주어질 때, 1번 도시에서 $N$번 도시까지 가는 최소 비용을 구하는 프로그램을 작성하시오.

첫째 줄에 도시의 수 $N$($2 \le N \le 2500$)과 도로의 수 $M$($1 \le M \le 4000$)이 주어진다. 둘째 줄에 각 도시 주유소의 리터당 가격이 도시 번호 순서대로 $N$개 주어진다. 리터당 가격은 1 이상 2500 이하의 자연수다. 다음 $M$개 줄에는 도로 하나의 정보가 자연수 세 개로 주어진다. 앞의 두 수는 도로가 잇는 두 도시의 번호이고, 세 번째 수는 도로의 길이다. 도로의 길이는 1 이상 2500 이하의 자연수다. 한 쌍의 도시를 잇는 도로는 많아야 하나다. 어떤 도시에서 다른 어떤 도시로든 도로를 따라 이동할 수 있다.

1번 도시에서 $N$번 도시까지 가는 최소 비용을 한 줄에 출력한다.