#include <bits/stdc++.h>

using namespace std;

int _distance(vector<int> d, vector<bool> separatedSet, int len){
    int min = INT_MAX;
    int min_index;

    for (int v = 0; v < len; v++){
        if (!separatedSet[v] && d[v] <= min){
            min = d[v];
            min_index = v;
        }
    }

    return min_index;
}

long leastTimeToInterview(int n, int k, int m) {
    vector<vector<int>> adj(n, vector<int>(n, 0));
    vector<int> distance(n, INT_MAX);
    vector<bool> spt(n, 0);

    distance[0] = 0;

    for(int i = 0; i<m; i++){
        int a, b, c;
        cin >> a >> b >> c;
        // Comparing
        if((c < adj[a-1][b-1] || adj[a-1][b-1] == 0) && a!=b){
            adj[a-1][b-1] = c;
            adj[b-1][a-1] = c;
        }

    }

    for (int i = 0; i < n-1; i++){

        int u = _distance(distance, spt, n);
        spt[u] = 1;

        int d = distance[u];

        if(distance[u]%(2*k)>=k){
            d = d + 2*k - distance[u]%(2*k);
        }


        for (int v = 0; v < n; v++){
            if (!spt[v] && adj[u][v] && distance[u] != INT_MAX && d + adj[u][v] < distance[v]){
                distance[v] = d + adj[u][v];
            }
        }

    }

    return distance[n-1];
}


int main()
{
    ofstream fout(getenv("OUTPUT_PATH"));

    int n;
    cin >> n;
    cin.ignore(numeric_limits<streamsize>::max(), '\n');

    int k;
    cin >> k;
    cin.ignore(numeric_limits<streamsize>::max(), '\n');

    int m;
    cin >> m;
    cin.ignore(numeric_limits<streamsize>::max(), '\n');

    long result = leastTimeToInterview(n, k, m);

    fout << result << "\n";

    fout.close();

    return 0;
}