Зам засварлах

2s

128MB

1380

0%

Graph Algorithms

$n$ хот, тэдгээрийн хооронд $m$ зам бий. Гэтэл замуудын байдал нь ашиглах боломжгүйтэй тэнцэхүйц муу байна. Зарим замуудыг засаж, ямар ч хоёр хотын хооронд тохиромжтой чиглэл байлгана.

Зам бүрийн засварын өртөг мэдэгдэж байгаа; нийт өртөг хамгийн бага байх шийдийг ол.

https://cses.fi/problemset/task/1675

Оролтын формат

Эхний мөрөнд $n$ ба $m$ хоёр бүхэл тоо байна: хот болон замын тоо. Хотууд $1,2,\dots,n$ гэж дугаарлагдсан.

Дараа нь замуудыг тодорхойлсон $m$ мөр байна. Мөр бүрт $a$ , $b$ , $c$ гурван бүхэл тоо байна: $a$ ба $b$ хотуудын хооронд зам байгаа бөгөөд засварын өртөг нь $c$ . Зам бүр хоёр чиглэлтэй.

Зам үргэлж хоёр өөр хотыг холбодог бөгөөд хоёр хотын хооронд хамгийн ихдээ нэг зам байна.

Гаралтын формат

Нэг бүхэл тоо хэвлэ: хамгийн бага нийт засварын өртөг. Харин шийд байхгүй бол "IMPOSSIBLE" хэвлэ.

Хязгаарлалт

$1 \le n \le 10^5$
$1 \le m \le 2 \cdot 10^5$
$1 \le a,b \le n$
$1 \le c \le 10^9$

Жишээ

Оролт1

Гаралт1

0.1 / 64 KiB

Редактор уншиж байна...