[W] Worldwide Wandering

bye17과 hi12는 세계 여행을 다니기로 했다. 하지만 모든 나라를 방문하기에는 돈이 너무 많이 들 것 같아, 일부 나라만 골라서 여행하기로 했다.

bye17과 hi12는 $1$번 나라에 살고 있기 때문에, 여행은 $1$번 나라에서 시작해 $1$번 나라로 끝나야 한다. 또한 $1$번 나라를 제외하고 적어도 하나의 나라를 방문해야 한다.

bye17과 hi12가 사는 세계에는 $N$개의 나라가 있으며, 각 나라에는 $1$번부터 $N$번까지의 번호가 있다. 만약 bye17과 hi12가 $2\le i\le N$인 $i$번 나라를 방문한다면, 해당 나라에서 $T\_i$시간동안 머무르기로 계획했다.

bye17과 hi12가 사용할 수 있는 항공편은 $M$개가 있으며, $j$번째 항공편은 $v\_j$번 나라에서 $w\_j$번 나라로 가는 단방향 항공편을 제공한다. 해당 항공편을 타고 이동할 때는 $F\_j$시간이 걸린다. 요즘 세상은 강하게 연결되어 있으므로, 항공편을 적절히 사용해서 임의의 두 나라 간의 이동이 가능하다.

bye17과 hi12는 아직 돈이 많지 않은 관계로 이번 여행에서는 항공편을 최대한 적게 타면서 여행하기로 했다. 그런데 bye17은 이번 여행을 짧고 굵게 즐기고 싶어 해서 그중 시간이 가장 짧게 걸리는 경로를 선택하기로 했다. 반면 hi12는 여행을 최대한 오래 즐기고 싶어 해서 시간이 가장 오래 걸리는 경로를 선택하기로 했다.

나라에서 머무르는 시간과 항공편을 타는 데 걸리는 시간만 고려할 때, bye17과 hi12가 각각 선택할 경로를 알아보자!

첫째 줄에는 나라의 개수 $N$과 항공편의 개수 $M$이 공백으로 구분되어 주어진다. $(2\le N\le 200\\, 000;$ $0\le M\le 500\\, 000)$

둘째 줄에는 각 나라에서 머무를 시간을 의미하는 $N-1$개의 정수 $T\_2,\ldots ,T\_N$이 공백으로 구분되어 주어진다. $(1\le T\_i\le 10^6)$

셋째 줄부터 $M$개의 줄에 걸쳐, $j+2$번째 줄에는 항공편의 정보를 의미하는 세 정수 $v\_j$, $w\_j$, $F\_j$가 공백으로 구분되어 주어진다. $(1\le v\_j,w\_j\le N;$ $v\_j \neq w\_j;$ $1\le F\_j\le 10^6)$

첫째 줄에는 bye17의 여행 계획에 따라 여행할 때 걸릴 시간을 출력한다.

둘째 줄에는 hi12의 여행 계획에 따라 여행할 때 걸릴 시간을 출력한다.