Для физической подготовки $N$ коров ($(2 \le N \le 1,000,000)$) проводят эстафету по $T$ тропам ($(2 \le T \le 100)$) пастбища.

Тропа соединяет разные перекрёстки ($(1 \le I1_i \le 1,000; 1 \le I2_i \le 1,000)$), каждый — конец хотя бы двух троп. Известны длина $length_i$ ($(1 \le length_{i} \le 1,000)$) и оба конца; двух троп между одной парой нет. Это математический граф.

$N$ коров располагаются на перекрёстках, возможно несколько на одном. Нужна правильная передача палочки от коровы к корове до финиша.

Помогите расстановке: кратчайший путь от $S$ до $E$ ровно по $N$ тропам.

Входные данные

• Строка $1$: целые $N$, $T$, $S$, $E$ через пробел.

• Строки $2..T+1$: строка $i+1$ описывает тропу $i$ целыми $length_i$, $I1_i$, $I2_i$ через пробел.

Выходные данные

• Строка $1$: одно целое, кратчайшее расстояние $S$ — $E$ ровно по $N$ тропам.

Примеры

Входные данные 1

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

Выходные данные 1

10

Автор задачи: Erik Bernhardsson, 2003