난쿤이는 7과 4를 좋아한다. 그래서 7과 4로만 이루어진 수를 행운수라고 한다.

난쿤이는 세계일주 게임을 한다. 모든 나라는 길이가 양수인 양방향 도로로 연결되어 있고, 도로는 트리 구조를 이룬다.

난쿤이는 어떤 세 나라 (A,B,C)가 존재하여 A에서 B로 가는데 무조건 길이가 행운수인 도로를 거쳐야 하고, A에서 C로 가는데도 무조건 길이가 행운수인 도로를 거쳐야 하는 순서쌍 (A,B,C)의 개수를 구하고 싶다. 여러분의 도움이 필요하다.

(단,(1,2,3),(1,3,2),(2,1,3),(2,3,1),(3,1,2),(3,2,1)은 모두 다른 순서쌍이다.) 그리고 A,B,C 는 서로 다른 세 나라이다.

입력

• 첫 줄에 나라의 수 N이 주어진 다.( 1<= N <= 10^5)
• 그 다음 N-1개 줄마다 Ai,Bi,Ci가 주어진다. (1 <= Ai,Bi <= N,1 <= Ci <= 10^9) (Ai와 Bi에 연결된 도로의 길이가 Ci이고 같은 도로는 2번이상 주어지지 않는다.)

출력

입출력 예

입력

4 
1 2 4 
3 1 2 
1 4 7 

출력

16 

입력

4 
1 2 4 
1 3 47 
1 4 7447 

출력

24 

출처:code forces
추천:ainta