採用する \(K-1\) 個の頂点集合 \(A\) を全探索します。\(A\) に関する誘導部分グラフの最小全域木の重みを \(x\) とし、端点がそれぞれ \(A,~ \{1, \cdots, N\} \setminus A\) に属する辺の重みの最小値を \(y\) として、\(x+y\) の取りうる最小値は答えと一致します。

配列を用いる Prim 法により \(x\) の値は \(O(K^2)\) で求まります。一方の端点が \(i\) である辺のうち、重みが小さい \(K\) 個を事前に計算しておくことで、\(y\) の値は \(O(K^2)\) で求まります。以上から、全体の計算量は \(\displaystyle O\left(K^2 \binom{N}{K-1} + N^2 \log N \right)\) となり十分高速です。

ちなみに \(\displaystyle 4^2 \binom{300}{3} \approx 7.13 \times 10^7,~ 5^2 \binom{80}{4} \approx 3.95 \times 10^7\) です。

実装例 (Rust 162ms https://atcoder.jp/contests/awc0150/submissions/78947785)

use proconio::{input, marker::Usize1};
use itertools::Itertools; // for collcet_vec, combinations, min_by_key

const INF: u64 = 1<<60;

fn main() {
    input! { N: usize, M: usize, K: usize, UVW: [(Usize1, Usize1, u64); M] }
    let mut E = vec![vec![INF; N]; N];
    for (u, v, w) in UVW {
        E[u][v] = w;
        E[v][u] = w;
    }
    
    let mut Y = vec![];
    for i in 0..N {
        let mut tmp = (0..N).map(|j| (E[i][j], j)).collect_vec();
        tmp.sort();
        tmp.truncate(K);
        Y.push(tmp);
    }
    
    let mut ans = INF;
    let mut seen = vec![false; K-2];
    let mut cost = vec![INF; K-2];
    
    for A in (0..N).combinations(K-1) {
        let mut x = 0;
        seen.fill(false);
        for i in 0..K-2 { cost[i] = E[A[K-2]][A[i]]; }
        for _ in 0..K-2 {
            let i = (0..K-2).filter(|&i| !seen[i]).min_by_key(|&i| cost[i]).unwrap();
            x += cost[i];
            seen[i] = true;
            for j in 0..K-2 { cost[j] = cost[j].min(E[A[i]][A[j]]); }
        }
        
        let mut y = INF;
        for &i in &A {
            for &(w, j) in &Y[i] {
                if !A.contains(&j) { y = y.min(w); break; }
            }
        }
        
        ans = ans.min(x+y);
    }
    
    println!("{ans}");
}