In a far away galaxy there are n inhabited planets numbered with numbers from 1 to n. One day the presidents of all the n planets independently from each other came up with an idea of creating the Galaxy Union. Now they need to share this wonderful idea with their galaxymates, that’s why each president is busy working out a project of negotiating with the other presidents.

For negotiations between some pairs of the planets there are bidirectional communication channels, each of which is characterized with "dial duration" t_i which, as a rule, takes several hours and exceeds the call duration greatly. Overall the galaxy has n communication channels and they unite all the planets into a uniform network. That means that it is possible to phone to any planet v from any planet u, perhaps, using some transitional planets v₁, v₂, ..., v_m via the existing channels between u and v₁, v₁ and v₂, ..., v_m - 1 and v_m, v_m and v. At that the dial duration from u to v will be equal to the sum of dial durations of the used channels.

So, every president has to talk one by one to the presidents of all the rest n - 1 planets. At that the negotiations take place strictly consecutively, and until the negotiations with a planet stop, the dial to another one does not begin. As the matter is urgent, from the different ways to call the needed planet every time the quickest one is chosen. Little time is needed to assure another president on the importance of the Galaxy Union, that’s why the duration of the negotiations with each planet can be considered equal to the dial duration time for those planets. As the presidents know nothing about each other’s plans, they do not take into consideration the possibility that, for example, the sought president may call himself or already know about the founding of the Galaxy Union from other sources.

The governments of all the n planets asked you to work out the negotiation plans. First you are to find out for every president how much time his supposed negotiations will take.