TB is going to hold a tea party at R318 of South Tower!

The tea party is so popular that there are  students present. However, they soon discover that R318 has no chair, not a single one. Luckily, they can seek for chairs at other rooms of South Tower.

There are totally  rooms in South Tower, including R318. For convenience, R318 is labeled as room  among these  rooms.

These rooms are connected by exactly  corridors, where each corridor has its own length.

That is to say, all rooms form a tree rooted room  with weighted edges.

Now, each student is going to set off for exactly one chair and return to R318.

All students move in the same pace. It takes a student exactly  seconds to walk through an edge with length  (from one end to another end).

Room  can provide at most  chairs, and has a congestion value  .

For those rooms that possess at least 1 chair, the first student who arrives at the room can take away that first chair immediately.

However, if another student wants to take a chair from the same room, suppose the previous chair was taken away at moment , he or she must wait until moment  or later to take his or her chair.

TB must begin the tea party as soon as possible. Please help him find the shortest time such that every student can return to R318 with a chair within time limitation. If the number of chairs in South Tower is not enough for these  students, output "Too many students!" (without quotes).

Note that a student carrying a chair moves as fast as a student that does not carry one. Each student can operate at most 1 chair in the whole process. Time used in irrelevant processes such as picking up a chair can be ignored.