#include <iostream>
#include <vector>
#include <cstring>
#include<stdio.h>
using namespace std;

void add(int nod,int val);
void rmv(int nod);
void sift(int nod);
void percolate(int nod);
void swap_nodes(int nod1,int nod2);
void dijkstra(int start);

struct
{
    int nod,cost;
}heap[50001];
int N=0;
int shortestPath[50001];
int poz[50001];
class Muchie {
    public:
        int Vec;
        int Cost;
        Muchie () {
            Vec = 0;
            Cost = 0;
        }
        Muchie (int v, int c) {
            Vec = v;
            Cost = c;
        }
};

vector<Muchie> v[50001];

bool DoubleChain;
int Chain[50001];
int Chain2[50001];
int ChainLevel;
int Chain2Level;

int main () {
    //freopen("dijkstra.in","r",stdin);
    //freopen("dijkstra.out","w",stdout);
    cin.tie(0);
    ios::sync_with_stdio(false);
    int Noduri, Muchii,Ka;
    cin >> Noduri >> Ka>>Muchii;

    for (int i = 0; i < Muchii; i++) {
        int orig, dest, cost;
        cin >> orig >> dest >> cost;
        v[orig].push_back(Muchie(dest, cost));
        v[dest].push_back(Muchie(orig,cost));
    }
    shortestPath[1]=0;
    add(1,0);

    for(int i=2;i<=Noduri;i++)
    {
        shortestPath[i]=1000000000;
        add(i,1000000000);
    }

    while(N>0)
    {
        int nod=heap[1].nod;
        int cost=heap[1].cost;
        rmv(1);

        for(int i=0;i<v[nod].size();i++)
        {
            int vec=v[nod][i].Vec;
            int cmp;
            if((shortestPath[nod]/Ka)%2==1)
            {
                cmp=(shortestPath[nod]/Ka)*Ka+Ka;
            }
            else
            {
                cmp=shortestPath[nod];
            }
            if(shortestPath[vec] > cmp+ v[nod][i].Cost)
            {
                shortestPath[vec]=v[nod][i].Cost+cmp;
                heap[poz[vec]].cost=shortestPath[vec];
                percolate(poz[vec]);
            }
        }
    }
    std::cout<<shortestPath[Noduri];
}

void add(int nod,int val)
{

    heap[++N].cost=val;
    heap[N].nod=nod;
    poz[nod]=N;
    percolate(N);
}

void rmv(int nod)
{
    swap_nodes(nod,N);
    N--;

    if(nod>1 && heap[nod].cost<heap[nod/2].cost)
    {
        percolate(nod);
    }
    else
    {
        sift(nod);
    }
}

void sift(int nod)
{
    int son=0;
    do
    {
        son=0;
        if(2*nod+1<=N)
        {
            if(heap[2*nod+1].cost<heap[2*nod].cost)
            {
                son=2*nod+1;
            }
            else
            {
                son=2*nod;
            }
        }
        else if(2*nod<=N)
        {
            son=2*nod;
        }
        if(heap[nod].cost<heap[son].cost)
        {
            son=0;
        }
        if(son)
        {
            swap_nodes(nod,son);
            nod=son;
        }
    }while(son);
}

void percolate(int nod)
{
    while(nod>1 && heap[nod].cost<heap[nod/2].cost)
    {
        swap_nodes(nod,nod/2);
        nod/=2;
    }
}

void swap_nodes(int nod1,int nod2)
{
    std::swap(poz[heap[nod1].nod],poz[heap[nod2].nod]);
    std::swap(heap[nod1].nod,heap[nod2].nod);
    std::swap(heap[nod1].cost,heap[nod2].cost);
}