import std.algorithm, std.conv, std.range, std.stdio, std.string; alias Graph!(int, size_t) graph; void main() { auto rd1 = readln.split.to!(size_t[]), n = rd1[0], m = rd1[1], t = rd1[2]; auto e = new Edge[](m); foreach (i; 0..m) { auto rd2 = readln.splitter; auto src = rd2.front.to!size_t-1; rd2.popFront(); auto dst = rd2.front.to!size_t-1; rd2.popFront(); e[i] = Edge(src, dst, rd2.front.to!int); } auto v = t.iota.map!(_ => readln.chomp.to!size_t-1).array; v.sort(); auto calc1() { auto g = new int[][](n, n); foreach (ref r; g) r[] = graph.inf; foreach (i; 0..n) g[i][i] = 0; foreach (ref ei; e) g[ei.s][ei.t] = g[ei.t][ei.s] = ei.w; return graph.minimumSteinerTree(v, g); } auto calc2() { auto cb = ulong(0); foreach (vi; v) cb = cb.bitSet(vi); auto w = n.iota.setDifference(v).array; e.sort!"a.w < b.w"; auto u = n - t, ans = int.max; foreach (i; 0..1< cc.bitTest(ei.s) && cc.bitTest(ei.t)); auto uf = UnionFind!size_t(n), r = 0; auto check() { auto c = n; foreach (i; 0..n) if (cc.bitTest(i)) { auto d = uf.find(i); if (c != n && c != d) return false; c = d; } return true; } foreach (eci; ec) { if (!uf.isSame(eci.s, eci.t)) { uf.unite(eci.s, eci.t); r += eci.w; } } if (check) ans = min(ans, r); } return ans; } writeln(t <= 14 ? calc1 : calc2); } pragma(inline) { pure bool bitTest(T)(T n, size_t i) { return (n & (T(1) << i)) != 0; } pure T bitSet(T)(T n, size_t i) { return n | (T(1) << i); } pure T bitReset(T)(T n, size_t i) { return n & ~(T(1) << i); } pure T bitComp(T)(T n, size_t i) { return n ^ (T(1) << i); } import core.bitop; pure int bsf(T)(T n) { return core.bitop.bsf(ulong(n)); } pure int bsr(T)(T n) { return core.bitop.bsr(ulong(n)); } pure int popcnt(T)(T n) { return core.bitop.popcnt(ulong(n)); } } struct Edge { size_t s, t; int w; } template Graph(Wt, Node, Wt _inf = 10 ^^ 9) { import std.algorithm, std.array; const inf = _inf; Wt minimumSteinerTree(Node[] t, Wt[][] g) { auto n = g.length, nt = t.length; auto d = g.map!(i => i.dup).array; foreach (k; 0..n) foreach (i; 0..n) foreach (j; 0..n) d[i][j] = min(d[i][j], d[i][k] + d[k][j]); auto opt = new Wt[][](1< !l.empty); } }