Để rèn thể lực, $N$ bò ($(2 \le N \le 1,000,000)$) chạy tiếp sức trên $T$ đường ($(2 \le T \le 100)$) đồng cỏ.

Mỗi đường nối hai giao điểm khác nhau ($(1 \le I1_i \le 1,000; 1 \le I2_i \le 1,000)$), mỗi điểm là đầu ít nhất hai đường. Biết dài $length_i$ ($(1 \le length_{i} \le 1,000)$) và hai đầu, không hai đường trực tiếp giữa cùng cặp. Là đồ thị toán học.

$N$ bò đứng tại giao điểm, nhiều bò có thể cùng điểm. Cần xếp để truyền gậy từng bò tới đúng đích.

Giúp xếp: đường ngắn nhất từ đầu $S$ tới cuối $E$ qua đúng $N$ đường.

Dữ liệu vào

• Dòng $1$: số nguyên $N$, $T$, $S$, $E$ cách nhau.

• Các dòng $2..T+1$: dòng $i+1$ mô tả đường $i$ với $length_i$, $I1_i$, $I2_i$ cách nhau.

Dữ liệu ra

• Dòng $1$: một số nguyên, khoảng cách ngắn nhất $S$ tới $E$ qua đúng $N$ đường.

Ví dụ

Dữ liệu vào 1

2 6 6 4
11 4 6
4 4 8
8 4 9
6 6 8
2 6 9
3 8 9

Dữ liệu ra 1

10

Tác giả bài toán: Erik Bernhardsson, 2003