#include <bits/stdc++.h>
#define Hoshimachi signed
#define Suisei main
using namespace std;
#define int long long
#define pii pair<int,int>
const int N=105;
int n,m,k;
int dp[(1<<10)+5][N],f[(1<<10)+5];
vector<pii> adj[N];
inline bool getbit(int n, int k){
    return (n>>k)&1;
}
Hoshimachi Suisei(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    // freopen(".inp", "r", stdin);
    // freopen(".out", "w", stdout);
    cin>>n>>m>>k;
    for(int i=1; i<=m; i++){
        int u,v,w;
        cin>>u>>v>>w;
        u--,v--;
        adj[u].push_back({v,w});
        adj[v].push_back({u,w});
    }
    memset(dp,0x3f,sizeof(dp));
    for(int i=0; i<k; i++){
        dp[(1<<i)][i]=0;
    }
    for(int i=n-k; i<n; i++){
        dp[(1<<(i-(n-k)+k))][i]=0;
    }
    memset(f,0x3f,sizeof(f));
    for(int mask=0; mask<(1<<2*k); mask++){
        for(int sub=mask; sub>0; sub=(sub-1)&mask){
            for(int i=0; i<n; i++){
                dp[mask][i]=min(dp[mask][i],dp[sub][i]+dp[mask^sub][i]);   
            }
        }
        priority_queue<pii,vector<pii>,greater<pii>> q;
        for(int i=0; i<n; i++){
            q.push({dp[mask][i],i});
        }
        while(!q.empty()){
            auto [d,u]=q.top();
            q.pop();
            for(auto [v,w]:adj[u]){
                int nd=d+w;
                if(dp[mask][v]>nd){
                    dp[mask][v]=nd;
                    q.push({nd,v});
                }
            }
        }
    }
    for(int mask=0; mask<(1<<2*k); mask++){
        for(int sub=mask; sub>0; sub=(sub-1)&mask){
            f[mask]=min(f[mask],f[sub]+f[mask^sub]);   
        }
        int cnt1=0,cnt2=0;
        for(int i=0; i<k; i++){
            cnt1+=getbit(mask,i);
            cnt2+=getbit(mask,i+k);
        }
        if(cnt1==cnt2){
            for(int i=0; i<n; i++){
                f[mask]=min(f[mask],dp[mask][i]);
            }
        }
    }
    if(f[(1<<2*k)-1]>1e18) cout<<"No solution";
    else cout<<f[(1<<2*k)-1];
}