도미노 효과

도미노는 게임을 할 때만 쓰는 것이 아닙니다. 여러 개의 도미노를 조금씩 간격을 두고 한 줄로 세운 뒤 맨 앞의 것을 넘어뜨리면 나머지가 차례대로 넘어집니다. 도미노 효과라는 표현이 여기에서 나왔습니다.

조각이 몇 개뿐이라면 별 의미가 없지만, 1980년대 초에는 사람들이 이를 정반대 극단으로 밀어붙였습니다. 색과 재질이 서로 다른 수백만 개의 도미노로 강당 전체를 정교한 도미노 패턴으로 채워, 잠깐 동안만 존재하는 예술 작품을 만들어 냈습니다. 이런 설치물에서는 보통 한 줄이 아니라 여러 줄이 동시에 넘어졌기 때문에 타이밍이 매우 중요했습니다.

여러분이 할 일은 이러한 도미노 시스템이 주어졌을 때 마지막 도미노가 언제, 어디에서 넘어지는지 계산하는 프로그램을 작성하는 것입니다. 시스템은 여러 개의 핵심 도미노(key domino)가 여러 줄의 일반 도미노로 연결되어 이루어집니다. 핵심 도미노가 넘어지면 그 도미노에 연결된 모든 줄이 넘어지기 시작합니다(단, 이미 넘어지고 있는 줄은 제외합니다). 넘어지고 있는 줄이 아직 넘어지지 않은 다른 핵심 도미노에 도달하면, 그 핵심 도미노도 넘어지면서 자신에게 연결된 줄들을 다시 넘어뜨립니다. 한 줄은 양쪽 끝 어느 쪽에서든 넘어지기 시작할 수 있고, 심지어 양쪽 끝에서 동시에 넘어질 수도 있습니다. 이 경우 그 줄에서 가장 마지막에 넘어지는 도미노는 두 핵심 도미노 사이의 어딘가에 있습니다. 모든 줄은 일정한 속도로 균일하게 넘어진다고 가정합니다.

입력은 여러 개의 도미노 시스템으로 이루어집니다. 각 시스템의 첫 줄에는 두 정수, 즉 핵심 도미노의 개수 $n$ ($1 \le n < 500$)과 그들 사이를 잇는 줄의 개수 $m$이 주어집니다. 핵심 도미노는 $1$번부터 $n$번까지 번호가 매겨집니다. 임의의 두 핵심 도미노 사이에는 줄이 최대 하나만 존재하며, 도미노 그래프는 연결되어 있습니다. 즉, 어떤 핵심 도미노에서 시작하더라도 줄을 따라가면 다른 모든 핵심 도미노에 도달할 수 있습니다.

이어지는 $m$개의 줄에는 각각 세 정수 $a$, $b$, $l$이 주어지며, 이는 핵심 도미노 $a$와 $b$ 사이에 한쪽 끝에서 반대쪽 끝까지 넘어지는 데 $l$초가 걸리는 줄이 있다는 뜻입니다.

모든 시스템은 $1$번 핵심 도미노를 넘어뜨리는 것으로 시작됩니다.

입력은 0 0 한 줄(즉 $n = m = 0$인 빈 시스템)로 끝나며, 이 줄은 처리하지 않습니다.

각 시스템마다 먼저 System #k 형식의 줄을 출력합니다. 여기서 k는 시스템 번호로 $1$부터 시작합니다. 다음 줄에는 마지막 도미노가 넘어지는 시각을 소수점 아래 정확히 한 자리까지 반올림하여, 그 마지막 도미노의 위치와 함께 출력합니다. 모든 시각은 $0.5$의 배수이므로 소수점 아래 한 자리로 정확히 표현됩니다.

마지막 도미노는 어떤 핵심 도미노 위에 있거나, 한 줄의 중간(줄이 양쪽 끝에서 넘어져 가운데에서 끝나는 경우)에 있습니다. 다음 형식을 정확히 지켜 출력합니다.

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

가장 늦게 넘어지는 위치가 여러 개라면 다음 규칙으로 유일하게 정합니다. 핵심 도미노와 줄 중간이 같은 시각이면 핵심 도미노를 택하고, 핵심 도미노가 여럿이면 번호가 가장 작은 것을, 줄이 여럿이면 $a < b$로 정규화한 $(a, b)$ 쌍이 사전순으로 가장 작은 것을 택합니다. 서로 다른 시스템 사이에는 빈 줄을 하나 출력하되, 마지막 시스템 뒤에는 출력하지 않습니다.