Codeforces celebrates 10 years! We are pleased to announce the crowdfunding-campaign. Congratulate us by the link https://codeforces.com/10years.
×

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

D. Presents in Bankopolis

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputBankopolis is an incredible city in which all the *n* crossroads are located on a straight line and numbered from 1 to *n* along it. On each crossroad there is a bank office.

The crossroads are connected with *m* oriented bicycle lanes (the *i*-th lane goes from crossroad *u*_{i} to crossroad *v*_{i}), the difficulty of each of the lanes is known.

Oleg the bank client wants to gift happiness and joy to the bank employees. He wants to visit exactly *k* offices, in each of them he wants to gift presents to the employees.

The problem is that Oleg don't want to see the reaction on his gifts, so he can't use a bicycle lane which passes near the office in which he has already presented his gifts (formally, the *i*-th lane passes near the office on the *x*-th crossroad if and only if *min*(*u*_{i}, *v*_{i}) < *x* < *max*(*u*_{i}, *v*_{i}))). Of course, in each of the offices Oleg can present gifts exactly once. Oleg is going to use exactly *k* - 1 bicycle lane to move between offices. Oleg can start his path from any office and finish it in any office.

Oleg wants to choose such a path among possible ones that the total difficulty of the lanes he will use is minimum possible. Find this minimum possible total difficulty.

Input

The first line contains two integers *n* and *k* (1 ≤ *n*, *k* ≤ 80) — the number of crossroads (and offices) and the number of offices Oleg wants to visit.

The second line contains single integer *m* (0 ≤ *m* ≤ 2000) — the number of bicycle lanes in Bankopolis.

The next *m* lines contain information about the lanes.

The *i*-th of these lines contains three integers *u*_{i}, *v*_{i} and *c*_{i} (1 ≤ *u*_{i}, *v*_{i} ≤ *n*, 1 ≤ *c*_{i} ≤ 1000), denoting the crossroads connected by the *i*-th road and its difficulty.

Output

In the only line print the minimum possible total difficulty of the lanes in a valid path, or -1 if there are no valid paths.

Examples

Input

7 4

4

1 6 2

6 2 2

2 4 2

2 7 1

Output

6

Input

4 3

4

2 1 2

1 3 2

3 4 2

4 1 1

Output

3

Note

In the first example Oleg visiting banks by path 1 → 6 → 2 → 4.

Path 1 → 6 → 2 → 7 with smaller difficulity is incorrect because crossroad 2 → 7 passes near already visited office on the crossroad 6.

In the second example Oleg can visit banks by path 4 → 1 → 3.

Codeforces (c) Copyright 2010-2020 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Feb/24/2020 09:13:43 (h1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|