Айлчлах Хотууд

2s

512MB

2222

0%

Advanced Graph Problems

Та Сюрьяля хотоос Лехмяля хот руу онгоцоор хамгийн бага үнэтэй замаар аялахыг хүсэж байна. Ямар хотуудыг заавал дайрах вэ?

Эх сурвалж: cses.fi

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

Эхний мөрөнд $n$ , $m$ хоёр бүхэл тоо байна: хот болон нислэгийн тоо. Хотууд $1,2,\ldots,n$ гэсэн дугаартай. 1 дүгээр хот нь Сюрьяля, $n$ дүгээр хот нь Лехмяля.

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

Сюрьяля хотоос Лехмяля хот руу зам байдаг гэж үзэж болно.

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

Эхлээд $k$ бүхэл тоог хэвлэ: замд заавал орох хотын тоо. Дараа нь $k$ хотыг өсөх дарааллаар хэвлэ.

Хязгаарлалт

$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

4
1 3 4 5

0.1 / 64 KiB

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