Vé giảm giá


Submit solution

Points: 1
Time limit: 1.0s
Memory limit: 1G

Problem type

Phúc muốn di chuyển từ nhà đến trường. Biết được thành phố cậu đang sống có $N$ ga tàu. Có $M$ tuyến tàu hai chiều. Tuyến thứ $i$ di chuyển giữa hai ga $u_i$ và $v_i$. Chi phí để di chuyển trên tuyết thứ $i$ là $w_i$ đồng.

Biết được nhà cậu ở ga thứ $s$ và trường học cậu ở ga thứ $t$. Hãy tìm số tiền nhỏ nhất để Phúc di chuyển đến trường. Tuy nhiên, cậu có một phiếu giảm giá, cậu có thể sử dụng một lần và được miễn phí một tuyến đi.

Dữ liệu

  • Dòng đầu tiên chứa hai số nguyên $N, M \ (1\le 2N, M \le 2\times 10^5)$;
  • $M$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $u_i, v_i \ (1\le u_i, v_i \le N)$;
  • Dòng cuối cùng chứa hai số nguyên $s, t \ (1\le s,t \le N)$.

Dữ liệu đảm bảo không có hai cạnh nào trùng nhau.

Kết quả

  • Kết quả bài toán.

Ví dụ

Ví dụ 1

input

3 3
1 2 3
2 3 1
2 1 5
1 3

output

1

Comments

There are no comments at the moment.