P5096 [USACO04OPEN] Cave Cows 1

Few people know that cows are actually quite fond of exploring caves. Bessie is planning to visit her favorite cave, which has $N$ rooms ($1 \le N \le 100$) numbered $1..N$ and $M$ bidirectional corridors ($1 \le M \le 1000$) connecting pairs of different rooms. Room $1$ is the entrance to the cave. Two rooms are never directly connected by more than one corridor. Always planning ahead, Bessie previously deposited a bale of hay in each of $K$ ($1 \le K \le 14$) different rooms so she will have food available during her expedition. Of course just like people, every time Bessie consumes a bale of hay, her "fatness" index increases by one unit. When she enters the cave, her fatness index is $0$ units. Every corridor in the cave has a certain width; Bessie can only fit through a corridor if her fatness index is no larger than that corridor's width. Bessie wants to eat as much as possible during her trip into the cave but wants to make sure that she does not grow too fat and trap herself in the process (at the end of her trip she must exit the cave at room $1$). Help her determine the maximum amount of hay she can eat. Note that Bessie can decide to pass through a room containing a bale of hay without eating the hay, if she wishes.

* Line $1$: Three space-separated integers: $N$ , $M$, and $K$. * Lines $2..K+1$: Each of these lines contains the index ($1..N$) of a room containing a bale of hay. * Lines $K+2..K+M+1$: Each of these lines corresponds to a bidirectional corridor and contains three space-separated integers: indices of the two rooms connected by the corridor, and the corridor's integer width ($1..100$).

* Line $1$: A single integer giving the maximum number of bales of hay Bessie can eat and still successfully exit the cave.

### OUTPUT DETAILS: All corridors leaving the entrance room have width at most $3$. Thus, returning to that room Bessie must have eaten no more than $3$ bales. Combined with the bale in that room, $4$ is the maximum number of bales that can be consumed.