```go
package main

import (
	"bufio"
	"fmt"
	"os"
)

var (
	cost [85][85]int
	memo [85][85][2][85]int
)

func solve(i, j, dir, c int) int {
	if c == 0 {
		return 0
	}
	if j-i+1 < c {
		return 1e9
	}
	if memo[i][j][dir][c] != -1 {
		return memo[i][j][dir][c]
	}

	curr := 0
	if dir == 0 {
		curr = i - 1
	} else {
		curr = j + 1
	}

	res := int(1e9)
	for v := i; v <= j; v++ {
		if cost[curr][v] != 1e9 {
			ans1 := solve(i, v-1, 1, c-1)
			ans2 := solve(v+1, j, 0, c-1)
			mn := ans1
			if ans2 < mn {
				mn = ans2
			}
			if mn != 1e9 {
				if cost[curr][v]+mn < res {
					res = cost[curr][v] + mn
				}
			}
		}
	}

	memo[i][j][dir][c] = res
	return res
}

func main() {
	in := bufio.NewReader(os.Stdin)
	var n, k int
	if _, err := fmt.Fscan(in, &n, &k); err != nil {
		return
	}
	var m int
	if _, err := fmt.Fscan(in, &m); err != nil {
		return
	}

	for i := 0; i <= n+1; i++ {
		for j := 0; j <= n+1; j++ {
			cost[i][j] = 1e9
		}
	}

	for i := 0; i <= n+1; i++ {
		for j := 0; j <= n+1; j++ {
			for d := 0; d < 2; d++ {
				for c := 0; c <= k; c++ {
					memo[i][j][d][c] = -1
				}
			}
		}
	}

	for i := 0; i < m; i++ {
		var u, v, c int
		fmt.Fscan(in, &u, &v, &c)
		if c < cost[u][v] {
			cost[u][v] = c
		}
	}

	res := int(1e9)
	for v := 1; v <= n; v++ {
		ans1 := solve(1, v-1, 1, k-1)
		ans2 := solve(v+1, n, 0, k-1)
		mn := ans1
		if ans2 < mn {
			mn = ans2
		}
		if mn < res {
			res = mn
		}
	}

	if res == 1e9 {
		fmt.Println("-1")
	} else {
		fmt.Println(res)
	}
}
```