Building Completion Times

A company is developing a new strategy simulation game. The core systems are complete, and only balance tuning, such as race balance and total play time, remains.

Because actual play time depends on the situation, the company will approximate it by the minimum time needed to construct every building. Some buildings may require other buildings to be completed first, so the calculation is not always simple. For instance, a defensive building might require a production building to be built before construction can begin. Multiple buildings can be constructed at the same time.

Assume that resources are unlimited and that issuing a construction command takes no time.

The first line contains the number of building types N (1 <= N <= 500).

Each of the next N lines describes one building. The line starts with the time required to construct that building, followed by the numbers of buildings that must be completed before it can be built. Building numbers are from 1 to N, and each line ends with -1.

Each construction time is a positive integer not greater than 100000. Only inputs where every building can be completed are given.

Print N lines. On the i-th line, print the minimum time required for building i to be completed.