まず、選ぶ \(K\) 頂点は元のグラフ上で連結として良いです。

さらに、\(K\) 頂点は以下のいずれかと同型になります：

これらのグラフの形に絞り、\(K\) 頂点を探索すれば良いです。探索はグラフの中心とそれに近い頂点を全て試すと良いです。

これらのグラフの葉となる頂点はコストがなるべく小さいものを選べば良いことを利用することで高速化することができます。

実装例(Python3)

n, m, k = map(int, input().split())
g = [[] for _ in range(n)]
for _ in range(m):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    g[a].append((b, c))
    g[b].append((a, c))
for e in g:
    e.sort(key=lambda x: x[1])
ans = 10**18
if k <= 4:
    for e in g:
        if len(e) >= k - 1:
            ans = min(ans, sum(c for _, c in e[:k - 1]))
if k == 4:
    for x in range(n):
        for y, c in g[x]:
            for z, a in g[x][:3]:
                for w, b in g[y][:3]:
                    if len({x, y, z, w}) == 4:
                        ans = min(ans, c + a + b)
elif k >= 5:
    for e in g:
        if len(e) >= 4:
            ans = min(ans, sum(c for _, c in e[:4]))
    for x in range(n):
        for y, c in g[x]:
            for i, (z, a) in enumerate(g[x][:4]):
                for w, b in g[y][:4]:
                    for v, d in g[x][:i]:
                        if len({x, y, z, w, v}) == 5:
                            ans = min(ans, c + a + b + d)
    for x in range(n):
        for y, a in g[x]:
            for z, b in g[x]:
                if y < z:
                    for w, c in g[y][:4]:
                        for v, d in g[z][:4]:
                            if len({x, y, z, w, v}) == 5:
                                ans = min(ans, a + b + c + d)
print(ans)