The marathon takes place in the beautiful city of Pordenone, which is formed by $N$ intersections and $M$ bidirectional roads. Each road is exactly $w[i]$ meters long.

The marathon starts at intersection $0$ and ends at intersection $N-1$. Marathoners must go through $K$ checkpoints S[0], S[1], ... , S[K-1], however, they can run through any route between two consecutive checkpoints.

The marathon starts at intersection $0$ and ends at intersection $N-1$. Marathoners must go through $K$ checkpoints w[0], S[1] ... S[K-1], however, they can run through any route between two consecutive checkpoints.

William's plan is the following: