톰톰 크루즈
시간 제한1초메모리 제한1024 MB
가중 그래프에서 간선을 하나 이상 포함하는 단순 경로 중 간선 가중치 합과 양 끝 정점 가중치의 합이 최소가 되는 값을 구한다.
문제
기지에서 가니메데까지 여행을 떠나려 한다. 여행 내내 사용할 우주선이 있다. 가니메데까지 가는 데 드는 연료, 위성의 일부를 이동하는 데 드는 연료, 기지로 돌아오는 데 드는 연료가 각각 필요하다.
가니메데에는 방문할 수 있는 지점이 여러 개 있다. 가니메데의 지도는 그래프로 주어지며, 각 정점의 가중치는 해당 지점과 기지 사이를 이동하는 데 드는 연료의 양과 같다. 각 간선의 가중치는 그 간선으로 연결된 두 정점 사이를 어느 방향으로든 이동하는 데 드는 연료의 양과 같다. 여행이 합리적이려면 어떤 간선이나 정점도 두 번 방문하지 않아야 한다. 다만 간선은 최소한 하나는 지나야 한다.
이런 여행을 수행하는 데 필요한 최소 연료의 양은 얼마인가?
입력
입력의 첫 줄에는 두 정수 N과 M이 주어진다. 각각 정점의 수와 간선의 수이다 (1 ≤ N ≤ 10^4, 0 ≤ M ≤ min(N(N-1)/2, 2 · 10^4)). 다음 줄에는 N개의 정수 v_0, v_1, ..., v_{N-1}이 주어진다 (1 ≤ v_i ≤ 10^6). 각각 정점 0, 1, ..., N-1의 가중치이다. 그다음 M개의 줄에는 각각 세 정수 f_i, t_i, w_i가 주어진다 (0 ≤ f_i, t_i < N, 1 ≤ w_i ≤ 10^6). 각각 간선으로 연결된 두 정점과 그 간선의 가중치이다.
출력
여행에 필요한 최소 연료의 양을 출력한다.