题目描述

你知道吗？除了用来玩多米诺骨牌游戏，多米诺骨牌还能用于其他用途。拿一些多米诺骨牌，把它们竖着摆放成一排，彼此之间只留出很小的间距。如果你摆放得当，轻轻推倒第一块骨牌，就可以使其他所有骨牌依次倒下（这就是“多米诺效应”这个短语的由来）。

虽然只用几块多米诺骨牌做这件事有点毫无意义，但在 80 年代初，有些人走向了另一个极端。他们使用数百万块不同颜色和材质的多米诺骨牌，在整个大厅里摆出精心设计的骨牌图案，创造出了（短暂存在的）艺术作品。在这些构造中，通常不只是一排多米诺骨牌同时倒下，而是几排。正如你可以想象的那样，时机在这里是一个至关重要的因素。

现在你的任务是编写一个程序，对于给定的由多米诺骨牌组成的系统，计算出最后一块多米诺骨牌何时以及在何处倒下。该系统由几个“关键多米诺骨牌”组成，这些关键骨牌由普通多米诺骨牌组成的排连接起来。当一个关键多米诺骨牌倒下时，与该骨牌相连的所有排也会开始倒下（除了那些已经倒下的排）。当正在倒下的排到达其他尚未倒下的关键多米诺骨牌时，这些其他关键多米诺骨牌也会倒下，并引发与它们相连的排开始倒下。多米诺骨牌排可以从两端中的任意一端开始倒下。甚至有可能一排多米诺骨牌从两端同时开始倒下，在这种情况下，那一排中最后倒下的多米诺骨牌就在它的两个关键多米诺骨牌之间的某个位置。你可以假设骨牌排以均匀的速度倒下。

输入格式

输入文件包含多个多米诺骨牌系统的描述。每个描述的第一行包含两个整数：关键多米诺骨牌的数量 $n$$（1 <= n < 500）$和它们之间排的数量 $m$。关键多米诺骨牌从 1 到 $n$ 编号。任意一对关键多米诺骨牌之间最多有一排骨牌，并且多米诺骨牌图是连通的，也就是说，通过一系列多米诺骨牌排，从一个骨牌到其他任何一个骨牌至少有一种路径。

接下来的 $m$ 行，每行包含三个整数 $a$、$b$ 和 $l$，表示在关键多米诺骨牌 $a$ 和 $b$ 之间有一排骨牌，从一端到另一端倒下需要 $l$ 秒。

每个系统都是通过推倒编号为 1 的关键多米诺骨牌开始的。

文件以一个空的系统$（n = m = 0）$结束，这个空系统不需要处理。

输出格式

对于每个用例，输出一行，说明用例的编号（“System #1”、“System #2” 等）。然后输出一行，包含最后一块多米诺骨牌倒下的时间，精确到小数点后一位，以及最后一块多米诺骨牌倒下的位置，这个位置要么在一个关键多米诺骨牌处，要么在两个关键多米诺骨牌之间（在这种情况下，按升序输出这两个数字）。请遵循输出示例中显示的格式。测试数据将确保只有一个解决方案。在每个系统的输出之后输出一个空行。

2 1
1 2 27
3 3
1 2 5
1 3 5
2 3 5
0 0

System #1
The last domino falls after 27.0 seconds, at key domino 2.

System #2
The last domino falls after 7.5 seconds, between key dominoes 2 and 3.

来源

1996年西南欧洲区域竞赛