Domino Effect

Dominoes are not only for playing the game. Stand a number of them on end, a small gap apart, in a row; tip the first one, and the rest fall down one after another. This is where the phrase domino effect comes from.

With only a handful of tiles this is fairly pointless, but in the early 1980s people took it to the opposite extreme. Using millions of dominoes of different colors and materials, they filled whole halls with elaborate patterns of falling dominoes, creating short-lived works of art. In these constructions usually not one but several rows of dominoes were falling at the same time, so timing was an essential factor.

Your task is to write a program that, given such a system of rows formed by dominoes, computes when and where the last domino falls. The system consists of several key dominoes connected by rows of ordinary dominoes. When a key domino falls, all rows connected to it also start falling (except the ones that have already fallen). When the falling rows reach other key dominoes that have not fallen yet, those key dominoes fall as well and set off the rows connected to them. A row may start collapsing from either end, and it can even collapse from both ends at once, in which case the last standing domino of that row is somewhere between its two key dominoes. Assume that rows fall at a uniform rate.

The input contains descriptions of several domino systems. The first line of each description contains two integers: the number of key dominoes $n$ ($1 \le n < 500$) and the number of rows $m$ between them. The key dominoes are numbered from $1$ to $n$. There is at most one row between any pair of key dominoes, and the domino graph is connected; that is, from any key domino you can reach any other by following a series of rows.

Each of the following $m$ lines contains three integers $a$, $b$, and $l$, stating that there is a row between key dominoes $a$ and $b$ that takes $l$ seconds to fall from one end to the other.

Each system is started by tipping over key domino number $1$.

The input ends with a line 0 0 (an empty system with $n = m = 0$), which must not be processed.

For each system, first print a line System #k, where k is the system's number, starting from $1$. On the next line, print the time when the last domino finishes falling, rounded to exactly one digit after the decimal point, together with the location of that last domino. Every falling time is a multiple of $0.5$, so one decimal digit is exact.

The last domino is either at a key domino or inside a single row (when the row collapses from both ends and finishes in the middle). Use exactly these formats:

• The last domino falls after T seconds, at key domino d.
• The last domino falls after T seconds, between key dominoes a and b.

When several locations finish at the same latest time, break ties deterministically: prefer a key domino over the middle of a row; among tied key dominoes choose the smallest number; among tied rows choose the one whose pair $(a, b)$, normalized so that $a < b$, is smallest in lexicographic order. Print a blank line between consecutive systems, but not after the last one.