죽은 선인장의 사회

최근 애완 그래프를 찾는 사람이 늘고 있다. 이런 사람들은 그래프 중에서도 귀여운 외형을 가진 트리(Tree)를 특히 많이 찾으며, 수요의 대부분이 트리에 몰려 있다. 쿠는 오래전부터 애완 그래프를 팔아 온 업자인데, 그래프 중에서도 캑터스(Cactus)만 취급하는 별종이었다.

트리와 캑터스는 모두 그래프의 종류이다. 트리는 모든 정점이 연결되어 있으면서 단순 사이클이 없는 그래프이다. 캑터스는 모든 정점이 연결되어 있으면서 단순 사이클은 있되, 서로 다른 두 단순 사이클에 동시에 들어가는 간선이 없는 그래프이다. 예를 들어 보자.

그림에서 왼쪽 첫 번째는 트리, 두 번째는 캑터스, 세 번째는 트리도 캑터스도 아닌 그래프이다. 단순 사이클이 많아질수록 외형이 끔찍해진다.

쿠는 지난 25년간 애정으로 캑터스만 다뤄 왔지만 이제는 지쳐 버렸다. 애완 그래프에 관심을 갖는 사람이 늘어 가게에 손님이 많아졌어도, 다들 캑터스 모양이 징그럽다며 떠나 버려서 여전히 장사가 되지 않는다. 그래서 쿠는 캑터스 판매업을 접고 새로운 일을 시작하기로 했다. 캑터스의 간선 몇 개를 잘라내 트리로 만들어 파는 트리 판매업이다.

그래프는 아주 섬세한 생물이다. 간선의 중간을 그냥 자르면 잘린 곳부터 썩어 들어간다. 반대로 간선을 양 끝 정점에 가까운 곳에서 깨끗하게 자르면 상처가 아물고 끝난다. 따라서 간선은 전체를 잘라야 그래프가 썩지 않는다. 또한 간선을 잘라 그래프가 여러 부분으로 나뉘면, 나뉜 그래프는 모두 썩어 버린다. 그러므로 쿠는 모든 정점이 연결된 상태를 유지하면서 간선을 잘라야 한다.

간선을 자르면 그 간선이 연결되어 있던 두 정점에 상처가 하나씩 생긴다. 그래프의 억센 생명력은 이 상처를 곧바로 자가치유하여, 새 간선 하나와 그 끝의 새 정점 하나를 자라나게 한다. 각 간선과 정점에는 회복 수치가 있다. 잘라낸 간선의 회복 수치를 $R_e$, 상처가 난 정점의 회복 수치를 $R_v$라 하면, 상처 부위에서는 길이가 $R_e + R_v$인 간선과 그 끝의 정점이 자라서 상처가 아문다.

그림에서 빨간색 간선이 잘라내는 간선이고, 초록색 간선이 새로 자란 간선이다. 캑터스의 모든 단순 사이클에서 간선을 정확히 하나씩 잘라내면 트리가 된다. 사람들은 지름이 작은 트리를 좋아하는 경향이 있다. 트리의 지름은 정점과 정점 사이 최단 거리의 최댓값이다. 쿠는 잘 팔리는 트리를 만들기 위해, 만들어지는 트리의 지름이 최소가 되도록 캑터스의 간선을 잘라낼 것이다. 캑터스가 주어질 때, 쿠가 만들어낼 트리의 지름을 구하는 프로그램을 작성하라.

첫 줄에 캑터스의 정점 수 $N$($3 \le N \le 100{,}000$)과 간선 수 $M$($N \le M \le 150{,}000$)이 공백 하나로 구분되어 주어진다. 정점에는 1부터 $N$까지, 간선에는 1부터 $M$까지 번호가 붙는다.

둘째 줄에는 각 정점의 회복 수치 $R_{v,1}, R_{v,2}, \cdots, R_{v,N}$($0 \le R_{v,i} \le 10^9$)가 공백 하나로 구분되어 주어진다. $R_{v,i}$는 $i$번 정점의 회복 수치이다.

다음 $M$개의 줄 중 $i$번째 줄에는 $i$번 간선의 정보인 정수 네 개 $A_i$, $B_i$, $L_i$, $R_{e,i}$($1 \le A_i, B_i \le N$, $A_i \ne B_i$, $1 \le L_i, R_{e,i} \le 10^9$)가 공백 하나로 구분되어 주어진다. $A_i$와 $B_i$는 $i$번 간선이 잇는 두 정점의 번호이고, $L_i$는 간선의 길이, $R_{e,i}$는 간선의 회복 수치이다. 주어지는 그래프는 캑터스임이 보장되며, 같은 두 정점을 잇는 간선이 여러 번 주어지지 않는다.

첫 줄에 주어진 캑터스의 간선을 적절히 잘라 트리를 만들었을 때, 만들 수 있는 트리 중 가장 작은 지름을 출력한다.