## Problem Description

Farmer John is on a boat seeking fabled treasure on one of the N
(1 <= N <= 100) islands conveniently labeled 1..N in the Cowribbean
Sea.

The treasure map tells him that he must travel through a certain
sequence A_1, A_2, ..., A_M of M (2 <= M <= 10,000) islands, starting
on island 1 and ending on island N before the treasure will appear
to him. He can visit these and other islands out of order and even
more than once, but his trip must include the A_i sequence in the
order specified by the map.

FJ wants to avoid pirates and knows the pirate-danger rating (0 <=
danger <= 100,000) between each pair of islands. The total danger
rating of his mission is the sum of the danger ratings of all the
paths he traverses.

Help Farmer John find the least dangerous route to the treasure
that satisfies the treasure map's requirement.

## Input

There are multiple tests.
For each test, there contains three parts.

## Output

For each test, output the minimum danger that Farmer John can encounter while
obtaining the treasure.

## Sample Input

3 4
1
2
1
3
0 5 1
5 0 2
1 2 0

## Sample Output

7

## Hint

*INPUT DETAILS:*
There are 3 islands and the treasure map requires Farmer John to
visit a sequence of 4 islands in order: island 1, island 2, island
1 again, and finally island 3. The danger ratings of the paths are
given: the paths (1, 2); (2, 3); (3, 1) and the reverse paths have
danger ratings of 5, 2, and 1, respectively.

*OUTPUT DETAILS:*
He can get the treasure with a total danger of 7 by traveling in
the sequence of islands 1, 3, 2, 3, 1, and 3. The cow map's requirement
(1, 2, 1, and 3) is satisfied by this route. We avoid the path
between islands 1 and 2 because it has a large danger rating.

## Source

Summer Training Qualification I