Beacon Network

A legendary kingdom has a network of beacons used to warn the whole land quickly in an emergency.

Each beacon is guarded by one archer. The archer has a fixed number of arrows and an instruction list that gives the order in which they should consider shooting at other beacons once their own beacon is lit.

More precisely, when a beacon becomes lit, its archer scans the instruction list from left to right. Whenever the next beacon in that list is not lit yet, the archer shoots one arrow at it. This continues until the archer has no arrows left or there are no more possible targets. The archers are perfectly accurate, so every arrow reaches its target. The travel time of an arrow equals the Euclidean distance between the two beacons, and the time needed to shoot the arrows is negligible.

Initially, beacon 1 is lit at time 0. Given the positions of all beacons, the number of arrows for each archer, and every instruction list, compute the time at which each beacon becomes lit.

The first line contains the integer N, the number of beacons. (1 <= N <= 100) The beacons are numbered from 1 to N, and beacon 1 is already lit at time 0.

Each of the next N lines describes one beacon, in this order:

• integers X and Y (1 <= X, Y <= 1000): the coordinates of the beacon
• integer S (1 <= S <= 100): the number of arrows held by this beacon's archer
• N-1 distinct integers between 1 and N: this archer's instruction list

The instruction list never contains the archer's own beacon number, and no number appears twice. The input is chosen so that no two beacons become lit at the same time.

Output N numbers, one per line: the times at which beacons 1 through N become lit.

Answers within an absolute or relative error of 0.001 are accepted.