Cookie Caravan

Photo of cookies by Bicanski, CC0.

To escape the zombies, you are driving across the country with your friends and their small children. The only thing that will keep the children quiet is, of course, cookies. There are a number of cities on your map, connected by roads, and you know in advance exactly how many cookies will be required for each road.

Cookies only come in packs of $k$. Every time you need to hand out a cookie, you will take one from the currently open pack if there are any left. Otherwise, if the current pack is empty (or if it is the first cookie of the trip), you will open a new pack first and then hand out a cookie. You will never run out of packs—you can always stop along the way to purchase more if necessary.

When you reach your destination, there may still be some cookies remaining in the currently open pack. You certainly aren’t going to let the children eat them (driving in the car is the only time the children are allowed to eat cookies), and you don’t want to eat them yourself, but they will go stale now that the pack is already open. The only thing to do is to throw the remaining cookies in the trash. However, if the children see you throwing cookies away they will throw a screaming fit; the volume of the screaming will be directly proportional to the number of cookies thrown away.

Since screaming children are even worse than zombies, your goal is to reach your destination with as few leftover cookies as possible! You are even willing to drive a longer distance, including the possibility of driving right past the destination and returning to it later, in order to accomplish this (the children will be too busy eating cookies to notice). However, if there are multiple routes that all result in the minimum possible number of leftover cookies, you should choose the one that requires the fewest total cookies.

Input

The first line of input consists of three space-separated integers:

• $k$, the number of cookies in a pack ($1 \leq k \leq 100$)

• $n$, the number of cities on the map ($2 \leq n \leq 100$)

• $m$, the number of roads on the map ($1 \leq m \leq n(n-1)/2$)

After that, there are $m$ lines, one for each road. Each line contains three space-separated integers $a$, $b$, $c$, indicating a two-way road between cities $a$ and $b$ which requires $c$ cookies in either direction ($1 \leq c \leq 1\, 000$). Cities are numbered from $1$ to $n$; you may assume that no road connects a city to itself, and no two roads connect the same pair of cities.

You start in city $1$, and your destination is city $n$. There is guaranteed to be at least one path connecting $1$ to $n$.

Output

Output the length (measured in cookies) of a path from city $1$ to city $n$ which leaves the fewest possible number of leftover cookies in the currently open pack at the end of the trip. If there are multiple such paths, output the length of the shortest.

5 4 4
1 2 12
1 3 8
2 4 9
3 4 16

40

1 4 4
1 2 12
1 3 8
2 4 9
3 4 16

21