Pour leur forme physique, $N$ vaches ($(2 \le N \le 1,000,000)$) courent un relais sur les $T$ chemins ($(2 \le T \le 100)$) du pré.

Chaque chemin relie deux intersections distinctes ($(1 \le I1_i \le 1,000; 1 \le I2_i \le 1,000)$), chacune touchant au moins deux chemins. Longueur $length_i$ ($(1 \le length_{i} \le 1,000)$) et extrémités connues ; aucun couple n'a deux chemins directs. C'est un graphe mathématique.

Les $N$ vaches se placent aux intersections, parfois plusieurs au même endroit. Elles doivent bien se placer pour passer le témoin et atteindre l'arrivée.

Aidez-les : trouvez le plus court trajet entre $S$ et $E$ traversant exactement $N$ chemins.

Entrée

• Ligne $1$ : entiers $N$, $T$, $S$, $E$ séparés.

• Lignes $2..T+1$ : ligne $i+1$ décrit chemin $i$ par $length_i$, $I1_i$, $I2_i$ séparés.

Sortie

• Ligne $1$ : un entier, distance minimale de $S$ à $E$ via exactement $N$ chemins.

Exemples

Entrée 1

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

Sortie 1

10

Auteur du problème : Erik Bernhardsson, 2003