D. Пуужингийн үүр

хугацааны хязгаарлалт 2 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Бэрланд улс $1$-ээс $n$ хүртэл дугаарлагдсан $n$ хоттой. Тэдний зарим нь хоорондоо хоёр чиглэлт замаар холбогдсон. Зам бүр урттай. Мөн аль ч хотоос аль ч хотруу эдгээр замаар очиж чаддаг байна. "Супер Дупер" баримт бичгийн дагуу Бэрланд улс "Супер Дупер" пуужингуудаар хамгаалагдсан аж. Нууц "Супер Дупер" пуужингуудын үүрний байршил нууцлагдмал байдаг ч Боб зарим мэдээллийг олж чаджээ. Тэрхүү мэдээлэл үүрийг нийслэл хотоос яг $l$ зайд байгааг хэлж байв. Нийслэл хот нь $s$ дугаарын хот юм.

Бичиг баримт энгийн тодорхойлолт өгчээ: Нууц "Супер Дупер" пуужингийн үүр хаа нэгтээ байх гарцаагүй бөгөөд хүрэлцээтэй нөхцөл нь (хотод эсвэл зам дээр) энэ байршлаас замуудын дагуу нийслэл хүрэх хамгийн ойр зай нь $l$ байх явдал юм.

Боб Бэрландад хэчнээн пуужингийн үүр байгааг тодорхойлон дайсны тагнуулд мэдээллээ зарахыг хүсжээ. Бобд туслаарай.

Оролт

Эхний мөрөнд харгалзан хотын тоо, улс дахь замын тоо болон нийслэл хотын дугаарыг илэрхийлэх $n$, $m$ болон $s$ ($2 ≤ n ≤ 10^{5}; n-1 ≤ m ≤ min(10^5, \frac{n(n-1)}{2}); 1 ≤ s ≤ n$) тоонууд байна.

Дараагийн $m$ мөрөнд замуудын мэдээлэл байна. Мөр бүрт $v_{i}$, $u_{i}$, $w_{i}$ ($1 ≤ v_{i}, u_{i} ≤ n$, $v_{i} ≠ u_{i}$, $1 ≤ w_{i} ≤ 1000$) бүхэл тоонууд байх ба энэ нь $v_{i}$, $u_{i}$ хотууд $w_{i}$ урттай замаар холбогдсоныг илэрхийлнэ. Өгөгдлийн сүүлийн мөрөнд пуужингуудын үүр нийслэлээс хэр хол байгааг илэрхийлэх $l$ ($0 ≤ l ≤ 10^{9}$) тоо байна. Өгөгдөлд:

  • Хоёр хот хамгийн ихдээ нэг замаар холбогдсон байна;
  • Зам бүр ялгаатай хоёр хотыг холбоно;
  • Аль ч хотоос аль ч хотруу замуудын тусламжтайгаар очиж болдог байна.

Гаралт

Нууц "Супер Дупер" пуужингийн үүрийн тоог хэвлэнэ үү.

Орчуулсан: Бат-Од

Жишээ тэстүүд

Оролт
4 6 1
1 2 1
1 3 3
2 3 1
2 4 1
3 4 1
1 4 2
2
Гаралт
3
Оролт
5 6 3
3 1 1
3 2 1
3 4 1
3 5 1
1 2 6
4 5 8
4
Гаралт
3

Тэмдэглэл

Эхний жишээнд үүрнүүд $3$ болон $4$ дугаарын хотуудад болон $(1, 3)$ зам дээр $1$ дугаарын хотоос $2$ зайтай байрлана.

Хоёр дахь жишээнд нэг үүр нь $(1, 2)$ замын яг голд нь байна. Нөгөө хоёр үүр нь $(4, 5)$ зам дээр $4$ дүгээр хотоос $3$ зайд болон $5$ хотоос $4$ дүгээр хот руу явах замд $3$ зайд тус тус байрлана.

Сэтгэгдлүүдийг ачааллаж байна...