n = int(input())
k = int(input())
m = int(input())
e = [[] for _ in range(n+1)]
for _ in range(m):
    ot, ku, t = map(int, input().split())
    e[ot].append((ku, t))
    e[ku].append((ot, t))

from heapq import *
ans = [10**10]*(n+1)
ans[0], ans[1] = 0, 0
ch = [(0, 1)]
while ch:
    lt_snum = heappop(ch)
    l, num = lt_snum[0], lt_snum[1]
    if l > ans[num]:
        continue
    #print(ch)
    for nbr, s in e[num]:
        if nbr == n:
            #print(num, nbr, )
            if l+s < ans[nbr]:
                #print(num, nbr, l+s, 0)
                ans[nbr] = l+s
                heappush(ch, (l+s, nbr))
        elif (l+s)//k%2==0 and l+s < ans[nbr]:
            #print(num, nbr, l+s ,1)
            ans[nbr] = l+s
            heappush(ch, (l+s, nbr))
        else:
            if ((l+s)//k+1)*k < ans[nbr]:
                #print(num, nbr, ((l+s)//k+1)*k, 2)
                ans[nbr] = ((l+s)//k+1)*k
                heappush(ch, (((l+s)//k+1)*k, nbr))
print(ans[n])