Mudstock Bis

To celebrate the tenth anniversary of the first rally of its members on the common of Mudstock, the Holypolygons association is organizing a grand festival called Mudstock Bis.

The members live in many small settlements of Holypolyland spread along $\ell$ railway lines ($1 \le \ell \le 350$), numbered from $1$ to $\ell$. No line is longer than $500$ km. Every line starts at the capital and runs radially outward to the provinces, and the lines never cross. Except for the capital, each settlement lies on exactly one line. Each line has at least $1$ and at most $100$ settlements, and each settlement has at most $100$ members.

Every settlement other than the capital is identified by a pair of coordinates $(k, n)$, where $k$ is its line number and $n$ is its position along that line. Settlements on a line are numbered consecutively starting from the capital. The capital, which is the start of every line, has coordinates $(0, 0)$.

The association pays each member a train ticket for the trip home after the festival, and a ticket costs $1$ per kilometre travelled. You must choose where to hold the festival so that the total cost of everyone's trip home is as small as possible.

Write a program that reads the railway network, finds a settlement where holding the festival minimizes the total travel cost of all members, and reports that minimal total cost together with the chosen settlement.

The first line contains two integers: the number of railway lines $\ell$ ($1 \le \ell \le 350$) and the number of members living in the capital $m$ ($0 \le m < 100$).

Each of the next $\ell$ lines describes one railway line, in order from line $1$ to line $\ell$, as a sequence of integers separated by single spaces. The description starts with the number of settlements on that line (a positive integer, not counting the capital). Then, going outward from the capital, two integers are given for each settlement: the distance (a positive integer) from that settlement to the nearest settlement toward the capital (or to the capital itself), and the number of members living there (a non-negative integer).

On the first line, print the minimal total cost of all members' train trips home.

On the second line, print the coordinates $k$ and $n$ of a settlement where the festival should be held, separated by a single space; the capital is written as 0 0.

If several settlements give the same minimal total cost, print the one with the smallest line number $k$; if there is still a tie, print the one with the smallest position $n$. Under this rule the capital $(0, 0)$ is considered smaller than every other settlement, so the answer is unique.