알레르기가 있는 아론

말나르 씨의 옛 단짝 아론은 고향을 떠나 외딴섬에서 더 나은 미래를 찾았다. 왜 하필 그런 곳을 골랐는지 궁금할 텐데, 거대 기업의 품에서 성공하겠다는 대도시 대신 그런 곳을 택한 데에는 이유가 있다. 아론은 방울토마토와 자기가 몹시 알레르기를 겪는 돼지풀이 없는 곳에서 더 나은 미래를 찾고 있다. 말나르 씨는 아론을 골탕 먹이려고 자기 사무실에 돼지풀을 키웠다.

돼지풀은 나무가 아니지만, 말나르 씨의 식물은 n개의 정점이 (n − 1)개의 가지로 연결된 나무로 나타낼 수 있다. 나무는 방향이 없고 연결되어 있으며, 임의의 두 정점 사이에 유일한 경로가 존재하는 그래프이다. 알레르기 유발 물질은 가지에 집중되어 있지만 모든 가지가 같은 정도로 강한 것은 아니다. 말나르 씨는 정점 ui와 vi를 잇는 가지의 알레르기 수치가 wi임을 알고 있다. 그래서 식물에서 알레르기 수치가 가장 큰 연결된 가지 부분집합을 잘라낼 것이다. 부분집합의 알레르기 수치는 그 안의 가지 개수와, 그 부분집합에서 알레르기를 가장 적게 일으키는 가지, 즉 wi가 최소인 가지의 알레르기 수치를 곱한 값으로 정의한다. 말나르 씨는 실수하지 않으며, 가장 큰 알레르기 수치를 갖는 부분집합을 곧바로 찾아냈다.

그 부분집합의 알레르기 수치를 여러분도 구할 수 있는가?

첫째 줄에 자연수 n이 주어진다. (2 ≤ n ≤ 105)

다음 n − 1개 줄에 ui, vi, wi가 주어진다. (1 ≤ ui, vi ≤ n, ui ≠ vi, 1 ≤ wi ≤ 109) 이는 문제에서 설명한 나무의 가지를 나타낸다.

돼지풀 가지의 연결된 부분집합 중 알레르기 수치가 가장 큰 것의 알레르기 수치를 한 줄에 출력한다.