34941번 - 엽서 배달

시안이는 친구들에게 엽서를 선물하는 것을 좋아한다. 시안이가 사는 세상은 $N$개의 도시와 이들을 잇는 도로들로 구성되어 있으며, 트리 구조를 이룬다. 도시에는 $1, 2, \cdots, N$의 번호가 붙어 있으며, 각 도시에는 시안이의 소중한 친구들이 살고 있다.

시안이가 사는 세상의 도로는 방향에 따라 이동 비용이 달라진다. 도시 $u$와 도시 $v$를 잇는 도로는 $(u, v, w_u, w_v)$로 표현되며, $u$번 도시에서 $v$번 도시로 가는 비용은 $w_u$, 반대로 $v$번 도시에서 $u$번 도시로 가는 비용은 $w_v$임을 의미한다. 한 도시에서 다른 도시로 엽서를 보내는 비용은, 이동 경로에 포함된 모든 도로 비용의 합으로 정의된다.

시안이는 $N$개의 도시 중 한 곳을 우체국으로 선정하여, 그곳에서 다른 모든 도시에 살고 있는 친구들에게 엽서를 보내려 한다.

시안이는 우체국에서 다른 모든 도시로 엽서를 보내는 비용의 합이 최소가 되도록 우체국을 선정하려 한다. 이때 발생하는 비용을 구해보자.

첫 번째 줄에 도시의 개수 $N$이 주어진다. ($3 \le N \le 300\,000$)

두 번째 줄부터 $N - 1$개의 줄에 걸쳐 각 도로에 대한 정보 $u$, $v$, $w_u$, $w_v$가 차례대로 주어진다. ($1 \le u, v \le N; 1 \le w_u, w_v, \le 10^5$)

입력으로 주어지는 수는 모두 정수이다.

첫 번째 줄에 답을 정수 형태로 출력한다.