Gerald is positioned in an old castle which consists of n halls connected with n - 1 corridors. It is exactly one way to go from any hall to any other one. Thus, the graph is a tree. Initially, at the moment of time 0 , Gerald is positioned in hall 1 . Besides, some other hall of the castle contains the treasure Gerald is looking for. The treasure's position is not known; it can equiprobably be in any of other n - 1 halls. Gerald can only find out where the treasure is when he enters the hall with the treasure. That very moment Gerald sees the treasure and the moment is regarded is the moment of achieving his goal. The corridors have different lengths. At that, the corridors are considered long and the halls are considered small and well lit. Thus, it is possible not to take the time Gerald spends in the halls into consideration. The castle is very old, that's why a corridor collapses at the moment when somebody visits it two times, no matter in which direction. Gerald can move around the castle using the corridors; he will go until he finds the treasure. Naturally, Gerald wants to find it as quickly as possible. In other words, he wants to act in a manner that would make the average time of finding the treasure as small as possible. Each corridor can be used no more than two times. That's why Gerald chooses the strategy in such a way, so he can visit every hall for sure. More formally, if the treasure is located in the second hall, then Gerald will find it the moment he enters the second hall for the first time — let it be moment t 2 . If the treasure is in the third hall, then Gerald will find it the moment he enters the third hall for the first time. Let it be the moment of time t 3 . And so on. Thus, the average time of finding the treasure will be equal to . The first line contains the only integer n ( 2 ≤ n ≤ 10 5 ) — the number of halls in the castle. Next n - 1 lines each contain three integers. The i -th line contains numbers a i , b i and t i ( 1