17380번 - 죽은 선인장의 사회

최근, 애완 그래프를 찾는 사람이 많아지고 있다. 이런 사람들에게는 그래프 중에서 특히 귀여운 외형을 가진 트리(Tree)에 대한 수요가 많고, 수요의 대부분을 차지한다. 쿠는 예전부터 애완 그래프를 파는 업자였는데, 그래프 중에서도 특히 캑터스(Cactus)만 취급하는 별종이었다.

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

왼쪽에서 첫 번째 그림은 트리, 두 번째 그림은 캑터스, 세 번째 그림은 트리도 캑터스도 아닌 그래프를 나타낸다. 단순 사이클이 많아질수록 끔찍해지는 외형을 볼 수 있을 것이다.

쿠는 지난 25년간 애정으로 캑터스만을 다뤄왔지만, 이제는 지쳐버렸다. 애완 그래프에 관심을 가지는 사람들이 많아져 가게에 손님이 많아졌어도, 다들 캑터스는 모양이 징그럽다면서 떠나버리기 일쑤라 여전히 장사는 되지 않고, 생활은 점점 힘들어지고 있다. 그래서 쿠는 이제 냉엄한 현실과 타협하여 캑터스 판매업을 포기하고 새로운 시작을 하기로 했다. 바로 캑터스의 몇몇 간선을 잘라내 트리로 만들어 파는 트리 판매업을 하는 것이다.

그래프는 아주 섬세한 생물이기 때문에, 간선의 중간을 그냥 자르면 잘라낸 곳부터 썩어들어간다. 그러나 간선이 정점과 연결된 두 끝부분을 깨끗하게 잘라내면, 잘라낸 곳의 상처가 아물고 끝난다. 그래서 간선은 전체를 잘라내야 그래프가 썩지 않는다. 또한, 간선을 잘라내 연결이 끊어져 그래프가 여러 부분으로 나뉘면, 나뉜 그래프는 모두 썩어버린다. 그래서 모든 정점이 연결되어 있도록 철저히 관리하면서 간선을 잘라내야 한다.

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

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

첫 번째 줄에는 캑터스의 정점 수를 나타내는 정수 N(3 ≤ N ≤ 100,000)과 간선 수를 나타내는 정수 M(N ≤ M ≤ 150,000)이 공백 하나를 사이에 두고 주어진다. 각 정점에는 1 에서 N 사이의 번호가 붙고, 각 간선에도 1 에서 M 사이의 번호가 붙는다.

두 번째 줄에는 각 정점의 회복 수치를 나타내는 N개의 정수 R_v,1, R_v,2, ···, R_v,N(0 ≤ R_v,i ≤ 10⁹)가 공백 하나로 구분되어 주어진다. R_v,i는 i 번 정점의 회복 수치를 나타낸다.

다음 M 개의 줄의 i 번째 줄에는 i 번 간선의 정보를 나타내는 네 정수 A_i, B_i, L_i, R_e,i(1 ≤ A_i, B_i ≤ N, A_i ≠ B_i, 1 ≤ L_i, R_e,i ≤ 10⁹)가 공백 하나로 구분되어 주어진다. A_i와 B_i는 i 번 간선이 잇고 있는 두 정점의 번호를 나타내며, L_i는 i 번 간선의 길이, R_e,i는 i 번 간선의 회복 수치를 나타낸다. 주어진 그래프는 캑터스인 것이 보장되며, 같은 두 정점을 연결하는 간선이 여러 번 주어지지 않는다.

첫 번째 줄에 주어진 캑터스의 간선을 적절히 잘라 트리를 만들었을 때 가능한 최소의 지름을 가지는 트리의 지름을 출력한다.