Perpetuum Mobile

1902년이다. 알베르트 아인슈타인은 베른의 특허청에서 일하고 있다. 많은 특허 제안에는 어처구니없는 오류가 들어 있고, 심지어 에너지 보존 법칙을 위반하는 것도 있다. 설상가상으로 대부분의 제안은 미터법에 속하지 않거나 아예 문서화되지도 않은 비표준 물리 단위를 사용한다. 모든 제안은 다음 형태를 따른다.

• 모든 특허 제안에는 n개의 에너지 변환기가 들어 있다.
• 각 변환기에는 그것과 연관된, 알려지지 않은 입력 에너지 단위가 있다.
• 일부 에너지 변환기는 연결할 수 있다. 변환기 a를 변환기 b에 연결해서 a에 연관된 에너지 1단위가 b의 입력 단위 c개로 바뀐다면, 제안에는 호 a → b (c)로 표시된다. a의 출력은 a에서 b로 가는 그러한 호가 있을 때에만 b의 입력으로 쓸 수 있다.

아인슈타인은 에너지 변환기를 고리 모양으로 이어서 어떤 변환기에 되돌아 들어가는 에너지가 입력으로 주어진 에너지보다 많아지는, 즉 에너지 보존 법칙을 위반하는 제안을 모두 즉시 기각하려 한다.

아인슈타인의 조수들은 그가 잘못된 특허 제안을 걸러내는 일보다 더 큰일을 위해 태어났다는 것을 안다. 그래서 가장 어려운 사례는 조수들이 처리하고, 아인슈타인에게 주어지는 제안은 상당히 제한된 형태다. 아인슈타인에게 주어지는 모든 허용 가능한 특허 제안에는 호 가중치의 총곱이 0.9를 초과하는 고리가 존재하지 않는다. 반대로 아인슈타인에게 주어지는 모든 허용 불가능한 특허 제안에는 고리를 이루는 호의 개수가 제안에 정의된 변환기의 수를 넘지 않으면서 호 가중치의 총곱이 1.1 이상인 고리가 들어 있다.

아인슈타인이 허용 불가능한 제안을 가려내도록 도와줄 수 있는가?

입력은 다음과 같다.

• 두 정수 n과 m이 있는 한 줄. 여기서

  • n (2 ≤ n ≤ 800)은 에너지 변환기의 수다.
  • m (0 ≤ m ≤ 4000)은 호의 수다.

• 세 수 ai, bi, ci가 있는 m개의 줄. 여기서

  • ai와 bi (1 ≤ ai, bi ≤ n)는 에너지 변환기를 나타내는 정수다.
  • ci (0 < ci ≤ 5.0)는 소수로, 변환기 ai를 변환기 bi에 연결해서 ai에 연관된 입력 1단위가 bi에 연관된 ci단위로 변환됨을 나타낸다. ci는 소수점 이하 자릿수가 최대 4자리일 수 있다.

아인슈타인에게 주어진 제안이 허용 불가능하면 inadmissible, 그렇지 않으면 admissible을 한 줄에 출력한다.