Đường đi gần ngắn nhất (Almost Shortest Path)

Nguồn: UVa Online Judge

Phiên bản: Phước Hưng OJ Extended

Đề bài

Cho một đồ thị có hướng có trọng số dương, đỉnh xuất phát $S$ và đỉnh đích $D$.

Xét tất cả các đường đi ngắn nhất từ $S$ đến $D$. Mọi cạnh thuộc ít nhất một đường đi ngắn nhất như vậy đều bị loại bỏ.

Trên đồ thị còn lại, hãy tìm đường đi ngắn nhất từ $S$ đến $D$. Đường này được gọi là almost shortest path — đường đi gần ngắn nhất.

Input

Dòng đầu chứa hai số nguyên $N,M$.

Dòng thứ hai chứa hai số nguyên $S,D$.

Trong $M$ dòng tiếp theo, mỗi dòng chứa $U,V,P$, biểu diễn một cạnh có hướng từ $U$ đến $V$ có độ dài $P$.

Với mỗi cặp có thứ tự $(U,V)$, có nhiều nhất một cạnh từ $U$ đến $V$.

Phiên bản Phước Hưng OJ chứa đúng một test case; dòng kết thúc 0 0 của đề gốc đã được loại bỏ.

Output

In độ dài của đường đi gần ngắn nhất.

Nếu sau khi loại các cạnh thuộc mọi đường đi ngắn nhất không còn đường đi từ $S$ đến $D$, in -1.

Subtask

Trong tất cả các Subtask: $0\le S,D,U,V<N$; $S\ne D$; $U\ne V$; $1\le P\le10^3$; có nhiều nhất một cạnh có hướng từ $U$ đến $V$.

• Subtask 1 — 20% — 0.75 giây: $2\le N\le50$; $1\le M\le500$.
• Subtask 2 — 30% — 1.50 giây: $2\le N\le200$; $1\le M\le4000$.
• Subtask 3 — 50% — 3.00 giây: $2\le N\le500$; $1\le M\le10^4$.

Ví dụ

Input

7 9
0 6
0 1 1
0 2 1
0 3 2
0 4 3
1 5 2
2 6 4
3 6 2
4 6 4
5 6 1

Output

5

Giải thích

Các cạnh thuộc mọi đường đi ngắn nhất từ $0$ đến $6$ bị loại. Sau khi loại, đường đi tốt nhất còn lại có tổng trọng số $5$.