E. Ерөнхийлөгчийн айлчлал

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

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

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

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

Бэрланд улс $n$ хоттой ба $m$ замтай. Зам бүр хоёр хотыг холбох ба хоёр чиглэлтэй. Хоёр хотыг хамгийн ихдээ нэг л зам холбоно. Мөн бид зам бүрийн уртыг мэднэ.

Мөн бид удахгүй ерөнхийлөгчийг ямар нэгэн $s$ хотоос $t$ хот руу явах гэж байгааг мэднэ. Мэдээж тэрээр $s$ хотоос $t$ хот руу хамгийн дөт маршрутаар явна. Гэхдээ хэн ч түүний аль маршрутаар явахыг мэдэхгүй байв.

Аялал жуулчлалын сайд ерөнхийлөгчийг айлчлалынхаа үед замаас болж бухимдах вий гэж ихэд санаа зовж байв. Шалтгаан нь тэрээр ерөнхийлөгчийн дайран явж магадгүй хэсэг замыг засварлах гэж байгаа ажээ.

Энэхүү ажилд төсөв гаргах тийм ч амар биш. Ялгаатай $s, t$ ($s < t$) хос хот бүрт $s$ хотоос $t$ хот руу очих хамгийн богино маршрутын дагуух замуудын тоог ол.

Оролт

Эхний мөрөнд хотуудын тоо болон замуудын тоог илэрхийлэх $n, m$ ($2 ≤ n ≤ 500$, $0 ≤ m ≤ n \cdot (n - 1) / 2$) бүхэл тоонууд байна. Дараагийн $m$ мөрөнд замуудыг тайлбарлана. Тайлбар бүрт $x_{i}, y_{i}, l_{i}$ ($1 ≤ x_{i}, y_{i} ≤ n, x_{i} ≠ y_{i}, 1 ≤ l_{i} ≤ 10^{6}$) гэсэн гурван бүхэл тоо байх ба $x_{i}, y_{i}$ нь $i$-р замаар холбогдсон хотуудын дугаар ба $l_{i}$ түүний урт юм.

Гаралт

$c_{st}$ нь $s$ хотоос $t$ хотруу очих хамгийн богино маршрутын дагуух дан замуудын тоог илэрхийлдэг байхаар $c_{12}, c_{13}, ..., c_{1n}, c_{23}, c_{24}, ..., c_{2n}, ..., c_{n - 1, n}$ гэсэн $n\cdot(n-1)/2$ ширхэг тоон дарааллыг зайгаар тусгаарлан хэвлэ. Хэрэв $s$ хотоос $t$ хот руу очих зам байхгүй бол $c_{st} = 0$ гэж авна.

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

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

Оролт
5 6
1 2 1
2 3 1
3 4 1
4 1 1
2 4 2
4 5 4
Гаралт
1 4 1 2 1 5 6 1 2 1 
Сэтгэгдлүүдийг ачааллаж байна...