eolymp
bolt
Try our new interface for solving problems
Məsələlər

Модель железной дороги

Модель железной дороги

Zaman məhdudiyyəti 3 saniyə
Yaddaşı istafadə məhdudiyyəti 128 MiB

С детства Вас увлекали модели железных дорог. Создавать собственные пути, сложные перекрестки, вокзалы с миниатюрами путешественников, машинистов и багажа — это так весело! Однако для этого необходимо много места. Поскольку Ваш дом уже более чем полон, то Вы решили переехать в сад.

Вы уже вынесли все готовые треки наружу, когда заметили важный недостаток: поскольку раньше разные треки находились в разных комнатах, то имеются станции, до которых невозможно добраться друг от друга. Это следует изменить!

Положения станций уже зафиксированы. Длины всех возможных соединений, которые Вы можете построить, известны. Известны также соединенные между собой станции. Все соединения можно использовать в обоих направлениях. Вы можете удалить некоторые существующие соединения и вместо этого построить новые, но не более той же общей длины. Можно ли перестроить железные дороги так, чтобы до каждой станции можно было добраться со всех остальных?

Giriş verilənləri

В первой строке записаны три целых числа n~(2 \le n \le 5 \cdot 10^4), m~(0 \le m \le 2.5 \cdot 10^5) и l~(0 \le l \le m), где n — количество станций, m — количество возможных соединений и l — количество уже построенных соединений;

Следующие m строк описывают соединения. Каждое соединение описывается одной строкой с тремя целыми числами a, b~(1 \le a, b \le n) и c~(0 \le c \le 5 \cdot 10^3), описывающими, что существует соединение станции a со станцией b длиной c.

Первые l этих соединений уже существуют.

Çıxış verilənləri

Выведите "possible" если можно построить связную сеть, как описано выше. В противном случае выведите "impossible".

Nümunə

На рисунке 1 изображен первый тест. Можно соединить все станции, удалив соединения между станциями 1 и 2 длиной 2 и вместо этого построив соединение между станциями 2 и 4. Кривизна рельсов не имеет значения, ведь у вас есть молоток.

Во втором случае, изображенном на рисунке 2, невозможно соединить все три станции.

Giriş verilənləri #1
4 6 3
1 2 1
2 1 2
3 4 2
1 3 2
1 4 3
2 4 2
Çıxış verilənləri #1
possible
Giriş verilənləri #2
3 3 2
1 2 1
1 2 2
3 2 3
Çıxış verilənləri #2
impossible
Mənbə 2016 German Collegiate Programming Contest (GCPC), Problem E