С детства Вас увлекали модели железных дорог. Создавать собственные пути, сложные перекрестки, вокзалы с миниатюрами путешественников, машинистов и багажа — это так весело! Однако для этого необходимо много места. Поскольку Ваш дом уже более чем полон, то Вы решили переехать в сад.
Вы уже вынесли все готовые треки наружу, когда заметили важный недостаток: поскольку раньше разные треки находились в разных комнатах, то имеются станции, до которых невозможно добраться друг от друга. Это следует изменить!
Положения станций уже зафиксированы. Длины всех возможных соединений, которые Вы можете построить, известны. Известны также соединенные между собой станции. Все соединения можно использовать в обоих направлениях. Вы можете удалить некоторые существующие соединения и вместо этого построить новые, но не более той же общей длины. Можно ли перестроить железные дороги так, чтобы до каждой станции можно было добраться со всех остальных?
В первой строке записаны три целых числа , и , где — количество станций, — количество возможных соединений и — количество уже построенных соединений;
Следующие строк описывают соединения. Каждое соединение описывается одной строкой с тремя целыми числами и , описывающими, что существует соединение станции со станцией длиной .
Первые этих соединений уже существуют.
Выведите "possible" если можно построить связную сеть, как описано выше. В противном случае выведите "impossible".
На рисунке изображен первый тест. Можно соединить все станции, удалив соединения между станциями и длиной и вместо этого построив соединение между станциями и . Кривизна рельсов не имеет значения, ведь у вас есть молоток.
Во втором случае, изображенном на рисунке , невозможно соединить все три станции.