#include 
#include 
#include 
#include 


using namespace std;
int n, m, k;
vector > graph[40005];
vectorv;

struct node{
int idx;
int cost;
node(){
}
node(int _idx, int _cost){
idx=_idx;
    cost=_cost;
}
bool operator < (const node &temp) const{
    return cost > temp.cost;
}

};
int dist[40005];
vector > G[20];

long long dijsktra(int s){
bool visited[n + 5];

for(int i=0; i<=n; i++){
    visited[i]=false;
    dist[i] = 2e9;
}

priority_queuepq;
pq.push(node(s, 0));
    dist[s] = 0;
while(!pq.empty()){
    node c=pq.top();
    pq.pop();
    
    visited[c.idx]=true;
    for(int i=0; i c.cost + pom)){
        pq.push(node(sosed, pom));
        dist[sosed]=c.cost+pom;
    }
    }
}

    


    return 0;
}
int dp[16][1 << 16];
int travelling_salesmane(int node, int visited) {
    if(__builtin_popcount(visited) == 1) {
        for(int i = 0; i < G[node].size(); i++) {
            if(G[node][i].first == 0) {
                return G[node][i].second;
            }
        }
        return 0;
    }
    if(node == 0 and visited == 0) {
        return 0;
    }
    if(dp[node][visited] != -1) {
        return dp[node][visited];
    }
    int new_mask = visited;
    new_mask -= (1 << node);
    int result = 2e9;
    for(int i = 0; i < G[node].size(); i++) {
        int sosed = G[node][i].first;
        int weight = G[node][i].second;
        if(visited & (1 << sosed)) {
            result = min(result, travelling_salesmane(sosed, new_mask) + weight);
        }
    }
    return dp[node][visited] = result;
}
int main()
{
    cin>>n>>k>>m;
    for(int i=0; i>p;
    v.push_back(p);
    }
    
    
    for(int i=0; i>a;
    cin>>b >> c;
    
    graph[a].push_back(make_pair(b, c));
    graph[b].push_back(make_pair(a, c));
        
    }
    

    v.push_back(0);
    for(int i = 0; i < v.size(); i++) {
        dijsktra(v[i]);
        for(int j = 0; j < v.size(); j++) {
            if(v[i] != v[j]) {
                G[v[i]].push_back(make_pair(v[j], dist[v[j]]));
                G[v[j]].push_back(make_pair(v[i], dist[v[j]]));
                
            }
    }
    }
    
    int p = (int) v.size();
 
    for(int i = 0; i < v.size(); i++) {
        
        for(int j = 0; j < G[i].size(); j++) {
//            cout << i << " " << G[i][j].first << " " << G[i][j].second << endl;
        }
    }
    memset(dp, -1, sizeof dp);
    cout << travelling_salesmane(0, (1 << p) - 1) << endl;
    
    
    
   
    
    
    return 0;
}