어떤 나라에는 N 개의 도시가 있고, 각 도시는 1 번부터 N 번까지 번호가 붙어 있다.

또, 서로 다른 두 도시를 양방향으로 직접 연결하는 M 개의 도로가 있다.

도로들은 서로 길이가 다를 수 있다. 도로 길이의 단위는 km를 사용한다.

1번 도시에서 N 번 도시로 자동차를 이용하여 이동하려고 한다.

처음 출발할 때 자동차에는 기름이 없어서 주유소에서 기름을 넣고 출발하여야 한다.

기름통의 크기는 무제한이어서 얼마든지 많은 기름을 넣을 수 있다.

도로를 이용하여 이동할 때 1km마다 1리터의 기름을 사용한다.

각 도시에는 단 하나의 주유소가 있으며, 도시마다 주유소의 리터당 가격은 다를 수 있다.

가격의 단위는 원을 사용한다.

예를 들어, 이 나라에 다음 그림처럼 4개의 도시와 4개의 도로가 있다고 하자.

원 안에 있는 숫자는 도시의 번호, 원 옆에 있는 숫자는 그 도시에 있는 주유소의 리터당 가격이다.

도로 옆에 있는 숫자는 도로의 길이를 표시한 것이다.

1번 도시에서 출발할 때 7리터의 기름을 넣고 그 기름으로 4번 도시까지 (3번 도시를 거쳐) 이동하면 총 비용은 35 원이다.

만약 1번 도시에서 출발할 때 3 리터의 기름을 넣고(3 × 5 = 15원) 3번 도시로 이동한 다음,

다시 3번 도시에서 4 리터의 기름을 넣고(4 × 4 = 16원) 4번 도시에 도착하면 총 비용은 31 원이다.

또 다른 방법으로 1번 도시에서 2리터의 기름을 넣고(2 × 5 = 10원) 2번 도시로 이동하여,

2번 도시에서 9리터의 기름을 넣고(2 × 9 = 18원) 1번과 3번 도시를 거쳐 4번 도시에 도착하면 총 비용은 28원이다.

각 도시에 있는 주유소의 기름 가격과,

각 도로들의 길이를 입력으로 받아 1번 도시에서 N 번 도시로 이동하는 최소의 비용을 계산하는 프로그램을 작성하시오.

주유소(고등) timer 2초 memory 256MB

주유소(고등) 2초 256MB