굿점원

띵동~
"누구세요?"
"치킨배달 왔습니다."
"음? 치킨을 시킨 적이 없... 으아악!"

주문하지도 않은 치킨을 손님에게 배달해 주는 인호는 굿 점원이다. 인호는 일자로 뻗은 길을 따라 손님들에게 차례로 치킨을 선물한다.

어느 날 치킨을 배달할 집이 하나 늘었다. 인호는 새 손님에게 치킨을 배달하려고 길을 딱 하나만 새로 만들려고 한다. 친구들은 각자 자기가 만들 수 있는 길을 하나씩 알려주었다.

인호는 치킨가게를 0번 집이라 부르고, 가게에서 가까운 집부터 차례로 1번 집, 2번 집, 그렇게 n번 집까지 부른다. j번째 친구가 만드는 길은 $A_j$번 집과 $B_j$번 집을 잇고, 길이는 $C_j$이다. 새 집은 이 길 위에 있다.

인호는 0번 집에서 출발해 1번부터 n번까지 모든 집과 새 집에 치킨을 배달해야 한다. 걷는 규칙은 이렇다.

• 새로 만든 길이 잇는 두 집에서만 방향을 바꿀 수 있다.
• 막다른 길에 다다르면 되돌아간다. 0번 집과 n번 집이 막다른 길이다.
• 배달을 마친 뒤에도 새로 만든 길을 다 걷지 않았다면 남은 부분을 마저 걷는다. 그래서 새로 만든 길은 끝에서 끝까지 적어도 한 번은 걷는다.
• 모든 집에 치킨을 배달했고 새로 만든 길도 다 걸었다면 그 자리에서 멈춘다.

친구들이 알려준 길 중 하나를 골라 만들 때, 인호가 걷는 거리의 최솟값을 구하라.

첫째 줄에 인호가 원래 배달하던 집의 수 n과 길을 만들어 주는 친구의 수 m이 주어진다.

둘째 줄에 $i-1$번 집에서 $i$번 집까지의 거리 $L_i$가 $i = 1, 2, \dots, n$ 순서로 주어진다.

셋째 줄부터 m개의 줄에 걸쳐 j번째 친구가 만들 수 있는 길의 정보 $A_j\ B_j\ C_j$가 주어진다. 이 길은 $A_j$번 집과 $B_j$번 집을 잇고 길이는 $C_j$이다. $A_j$와 $B_j$는 항상 다르다.

$1 \le n, m \le 10000$, $1 \le L_i \le 100$, $1 \le A_j, B_j \le n$, $1 \le C_j \le 100$

새로운 길을 하나 만든 뒤, 인호가 모든 집에 치킨을 배달하려고 걷는 거리의 최솟값을 한 줄에 출력한다.

첫 번째 예제에서 두 번째 길, 즉 3번 집과 6번 집을 잇는 길이 5짜리 길을 만들고 0, 1, 2, 3, 새 집, 6, 5, 4 순서로 이동하면 25만큼 걸어 배달을 마칠 수 있다. 첫 번째 길을 만들면 32를 걸어야 한다.