Bankopolis 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*<sub class="lower-index">*i*</sub> to crossroad *v*<sub class="lower-index">*i*</sub>), 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*<sub class="lower-index">*i*</sub>, *v*<sub class="lower-index">*i*</sub>) &lt; *x* &lt; *max*(*u*<sub class="lower-index">*i*</sub>, *v*<sub class="lower-index">*i*</sub>))). 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.
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*<sub class="lower-index">*i*</sub>, *v*<sub class="lower-index">*i*</sub> and *c*<sub class="lower-index">*i*</sub> (1 ≤ *u*<sub class="lower-index">*i*</sub>, *v*<sub class="lower-index">*i*</sub> ≤ *n*, 1 ≤ *c*<sub class="lower-index">*i*</sub> ≤ 1000), denoting the crossroads connected by the *i*-th road and its difficulty.
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.
7 4
4
1 6 2
6 2 2
2 4 2
2 7 1
6
4 3
4
2 1 2
1 3 2
3 4 2
4 1 1
3
3 2
10
2 3 290
3 1 859
3 1 852
1 2 232
1 2 358
2 1 123
1 3 909
2 1 296
1 3 119
1 2 584
119
3 3
4
1 2 545
1 3 716
3 1 3
2 3 338
548
5 3
20
5 2 515
4 1 865
3 4 570
1 5 371
3 1 420
5 2 464
4 3 130
4 1 381
1 2 702
5 1 97
5 2 402
5 2 314
1 4 272
3 1 505
5 4 662
2 3 893
1 3 20
4 2 601
1 3 4
4 2 474
101
5 5
20
2 5 174
4 3 496
5 2 103
2 1 345
2 4 942
3 5 131
3 2 451
5 2 299
2 4 285
4 5 241
4 5 706
2 1 639
1 5 94
1 2 844
3 4 194
2 4 812
2 5 566
3 5 293
3 4 356
2 5 717
978
5 5
10
2 4 420
4 5 974
5 1 910
1 3 726
1 2 471
5 2 94
3 2 307
2 5 982
5 4 848
3 5 404
-1
3 2
4
2 3 716
3 2 239
3 2 646
3 2 39
39
5 4
4
5 4 614
4 1 177
1 3 66
5 2 43
857
10 4
10
1 4 662
4 7 555
7 9 172
1 8 481
8 10 609
1 2 705
1 10 225
8 2 939
2 10 329
6 10 477
1389
10 7
50
4 7 655
7 3 220
3 5 15
5 10 811
10 1 490
1 2 800
7 10 200
1 5 377
1 4 656
6 4 432
3 7 563
1 8 122
2 9 777
3 2 157
5 8 912
9 8 496
9 2 740
3 2 201
6 7 653
1 7 554
6 9 660
3 2 622
6 10 227
9 1 42
2 6 346
2 7 944
3 10 654
5 2 501
1 6 786
3 8 306
6 1 998
6 2 581
10 1 843
10 9 993
10 9 93
2 9 770
1 5 89
1 7 761
6 1 387
7 1 24
5 9 922
1 8 480
9 7 814
4 3 682
9 3 73
9 6 436
4 1 685
10 8 46
8 2 725
4 1 892
1760
6 4
10
2 5 609
5 6 805
6 4 814
5 6 322
4 3 689
4 6 30
2 1 949
2 1 650
2 4 217
4 2 362
1826
1 1
0
0
#include<bits/stdc++.h>

using namespace std;


int dp[82][82][82][82];
int n,k;
vector<pair<int,int> >g[2005];
#define INT_MAX 1000000000

int dfs(int start,int curr,int l,int rem)
{
    if(rem==0)
        return 0;
    int &ret=dp[start][curr][l][rem];
    if(ret!=-1)
        return ret;
     ret=INT_MAX;

    for(int i=0;i<g[curr].size();i++)
    {
        int v=g[curr][i].first;
        int cst=g[curr][i].second;
         if(v>start && v<l){
            ret=min(ret,cst+dfs(start,v,v,rem-1));
            ret=min(ret,cst+dfs(v,v,l,rem-1));
         }

    }
    return ret;
}
int main()
{
   memset(dp,-1,sizeof dp);
   cin>>n>>k;
   int num;
   cin>>num;
   for(int i=1;i<=num;i++)
   {
     int u,v,c;
     cin>>u>>v>>c;
     g[u].push_back(make_pair(v,c));

   }
    int res=INT_MAX;
    //cout<<res<<endl;

   for(int i=1;i<=n;i++)
   {
     res=min(res,dfs(0,i,i,k-1));
     res=min(res,dfs(i,i,n+1,k-1));
    // cout<<res<<"---"<<i<<endl;

   }


   if(res==INT_MAX)res=-1;
   cout<<res<<endl;


   return 0;

}
