상인

바이트랜드의 도시들은 도로로 연결되어 있으며, 임의의 두 도시 사이에는 (직접 이어지든 다른 도시를 거치든) 정확히 하나의 경로만 존재한다. 즉, 도로망은 트리를 이룬다.

한 상인이 돈을 벌기 위해 바이트랜드에 왔다. 그는 먼저 한 도시(출발 도시)에 자리를 잡은 뒤, 원하는 다른 한 도시(도착 도시)까지 이동한다. 바이트랜드의 법에 따라 이동 중 같은 도시를 두 번 지날 수 없으므로, 그의 이동 경로는 두 도시를 잇는 유일한 단순 경로가 된다.

각 도로에는 정해진 값이 있어, 그 도로를 지나면 상인은 그만큼의 이익을 얻는다. 값이 음수이면 그만큼 손해를 본다. 상인의 총 이익은 이동 경로에 포함된 모든 도로 값의 합이다. 총 이익이 가장 커지도록 출발 도시와 도착 도시를 정하라. 두 도시가 같아도 되며, 이때 상인은 어떤 도로도 지나지 않으므로 이익은 0이다.

첫째 줄에 도시의 수를 나타내는 정수 $n$ ($2 \le n \le 10^6$)이 주어진다. 도시는 $1$번부터 $n$번까지 번호가 매겨져 있다.

다음 $n - 1$개의 줄에는 각각 세 정수 $a$, $b$, $x$ ($-10^9 \le x \le 10^9$)가 주어진다. 이는 도시 $a$와 $b$를 잇는 도로가 있고, 그 도로를 지나면 상인이 $x$만큼 이익을 얻음을 뜻한다 (음수이면 손해).

상인이 얻을 수 있는 최대 총 이익을 정수 하나로 출력한다.