Vous et votre meilleur ami participez à un grand jeu de piste dans la forêt. Le but du jeu est de résoudre E énigmes (numérotées de 1 à E) posées par des organisateurs situés en différents lieux de la forêt, dont on vous fournit les coordonnées GPS. Atteindre les positions des énigmes n'est pas un problème, car vous disposez tous deux d'un ordinateur de poche dernier cri, avec géolocalisation, vous permettant à tout moment de visualiser votre position sur une carte détaillée de la forêt, ainsi que les positions de toutes les énigmes.

Toute la difficulté du jeu va donc consister à résoudre les énigmes. Aucun de vous deux n'est très doué pour le genre d'énigmes proposées dans ce jeu. La première énigme est toujours facile à résoudre, mais les autres sont quasiment introuvables sans un indice. Heureusement, une fois que vous avez résolu une énigme donnée, l'organisateur qui vous l'a posée vous donne un gros indice qui vous permet de résoudre facilement l'énigme suivante (par ordre de leur numéro).

Pour éviter de perdre du temps à chercher à résoudre les énigmes sans indices, vous décidez donc de les résoudre dans l'ordre de leur numéro. Les énigmes sont cependant placées de manière assez aléatoire dans la forêt, et les parcourir dans l'ordre demande de nombreux allers-retours.

Pour éviter de perdre trop de temps, vous et votre ami décidez de vous séparer, et de vous répartir les énigmes. Vous pouvez par exemple décider de résoudre toutes les énigmes paires, tandis que votre ami résoudra les énigmes impaires. Ainsi, dès que votre ami aura résolu l'énigme numéro 1, et obtenu l'indice pour l'énigme numéro 2, il vous l'enverra par mail via son ordinateur de poche, et vous pourrez alors résoudre cette énigme dès que vous aurez atteint sa position.

Vous décidez d'écrire un petit programme pour déterminer, à partir de la description de la carte et des positions des différentes énigmes, la meilleure répartition possible des énigmes entre vous et votre ami, c'est à dire celle qui permet de résoudre l'ensemble des énigmes en un minimum de temps.

Vous partez tous les deux de la position de l'énigme 1, et vous pouvez vous déplacer dans l'ensemble du graphe sans autre contrainte que le temps nécessaire pour parcourir chaque chemin. Vous pouvez traverser des énigmes sans les résoudre tout de suite, et pouvez également rester attendre sur une énigme en attendant de recevoir un indice.

Le jeu s'arrête lorsque vous résolvez la dernière énigme. On considèrera qu'une fois que vous êtes à la position où se trouve une énigme, et que vous ou votre ami avez résolu l'énigme précédente et obtenu l'indice, résoudre l'énigme suivante ne prend aucun temps. Seule l'énigme 1 peut être résolue sans indice.

On vous garantit qu'il est toujours possible de résoudre toutes les énigmes.

• 1 <= E <= 30, où E est le nombre d'énigmes.
• 1 <= C <= 450, où C est le nombre de chemins reliant chacun les emplacements de deux énigmes.
• 1 <= L <= 20, où L est le nombre de minutes pour parcourir un chemin.

Dans 30% des tests, on a E <= 15.

Dans 60% des tests (qui incluent les 30% précédents), on a C <= 50.

La première ligne de l'entrée contient deux entiers séparés par un espace : le nombre E d'énigmes, et le nombre C de chemins à double sens reliant ces énigmes. Deux énigmes ne peuvent être reliés que par un seul chemin.

Chacune des E lignes suivantes décrit un chemin, sous la forme de 3 entiers séparés par des espaces : les numéros des lieux reliés par le chemin, puis le temps nécessaire en minutes pour le parcourir.

Les chemins sont donnés dans un ordre quelconque.

Vous devez afficher un entier sur la sortie : le nombre minimal de minutes nécessaire pour résoudre toutes les énigmes dans l'ordre, en les répartissant au mieux entre vous et votre ami.

7 10
1 2 4
1 3 3
2 3 3
2 5 4
3 7 3
4 5 5
4 6 4
4 7 5
5 6 3
5 7 2

15

L'entrée correspond au dessin fourni dans la description du sujet.

Voici le parcours le plus rapide pour vous (P1) et votre ami (P2).

Détail du déroulement :

Temps	Evénement
0	P1 résout l'énigme 1 et part vers l'énigme 2. P2 part également de l'énigme 1, et se dirige vers l'énigme 3.
3	P2 arrive à l'énigme 3 mais ne la résout pas et repart aussitôt vers l'énigme 7.
4	P1 arrive à l'énigme 2 et la résout. Il obtient l'indice pour l'énigme 3 vers laquelle il se dirige.
6	P2 arrive à l'énigme 7 et repart aussitôt vers l'énigme 4.
7	P1 arrive à l'énigme 3, la résout, obtient l'indice de l'énigme 4 et le transmet à P2, puis part vers l'énigme 7.
10	P1 arrive à l'énigme 7 et repart aussitôt vers l'énigme 5.
11	P2 arrive à l'énigme 4 et la résout, puis envoie l'indice de l'énigme 5 à P1, et part vers l'énigme 6.
12	P1 arrive à l'énigme 5, la résout et envoie l'indice de l'énigme 6 à P2, puis repart vers l'énigme 7.
14	P1 arrive à l'énigme 7 et attend l'indice.
15	P2 arrive à l'énigme 6, la résout et envoie l'indice de l'énigme 7 à P1. P1 résout l'énigme 7. Le jeu de piste est terminé.