D. БэрДоналдс

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

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

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

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

БэрДоналдс нь, олонд танигдсан түргэн хоолны газар, Бэртаунд кафе нээхээр болов. Ганц чухал зүйл нь байршил сонгох байв. Бэртаунд $n$ замын уулзвар $m$ хоёр урсгалын зам байдаг. Зам болгоны уртыг бид мэдэж байгаа. Мөн аль ч хоёр замын уулзварыг холбосон зам байгаа (замуудаар дамжиж болно).

Таны даалгавар бол кафегаас хамгийн хол замын уулзвар нь хамгийн бага байхаар байршил сонгох юм. Жич кафег замын хажууд ч уулзварын дэргэд ч нээх боломжтой.

Оролт

Эхний мөрөнд уулзварын тоо $n$ болон замын тоо $m$ (enter image description here) өгөгдөнө. Дараагийн $m$ мөрний $i$ дахь мөрөнд Бэртауны $i$ дахь замыг тодорхойлох $a_i, b_i, w_i$ ($1 ≤ a_i, b_i ≤ n, a_i ≠ b_i; 1 ≤ w_i ≤ 10^5$) тоонууд өгөгдөнө. Энд $i$ дахь зам нь $a_i$ болон $b_i$ замын уулзваруудыг холбосон бөгөөд $w_i$ урттайг илэрхийлнэ.

Хоёр уулзварыг холбосон хамгийн ихдээ нэг зам байна. Мөн аль ч уулзвараас дурын уулзвар хүртэл зам олдоно.

Гаралт

Хамгийн хол замын уулзвар хүртэл зай болох бодит тоог хэвлэнэ.

Хариунд гарсан тоо нь $10^{-9}$ зэрэгт зөрөөгүй тохиолдолд зөв хариунд авч үзнэ.

Орчуулсан: Энхсанаа

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

Оролт
2 1
1 2 1
Гаралт
0.50
Оролт
3 3
1 2 1
2 3 1
1 3 1
Гаралт
1.00
Оролт
3 2
1 2 100
2 3 1
Гаралт
50.50
Сэтгэгдлүүдийг ачааллаж байна...