Moo Route

Bessie đang tìm lộ trình tối ưu giữa các thành phố. Có $N$ thành phố và $M$ đường kết nối chúng.

Hãy tìm đường đi ngắn nhất từ thành phố $s$ đến thành phố $t$.

Dữ liệu vào

Dòng đầu tiên chứa $N$, $M$, $s$, $t$ ($1\le N\le 100$).

$M$ dòng tiếp theo, mỗi dòng chứa $u$, $v$, $w$.

Dữ liệu ra

In ra độ dài đường đi ngắn nhất.

Ràng buộc

$1\le N\le 100$

Ví dụ