#include using namespace std; const int INF = 1 << 26; struct Edge { int u, v, c; bool operator<(const Edge& other) const { return c < other.c; } }; int N, M, T, ts[50]; Edge E[777]; int dist[50][50]; int root[50]; inline int find(int x){ if(x == root[x])return x; return root[x] = find(root[x]); } inline bool conn(int x, int y){ x = find(x); y = find(y); if(x == y)return false; root[x] = y; return true; } int rest_v[50]; int use[50]; inline int min_spanning_tree(int now){ for(int i=0;i= now)return INF; } } for(int i=0;i 0; k = (k - 1) & i){ dp[i][j] = min(dp[i][j], dp[k][j] + dp[i^k][j]); } } for(int j=0;j> N >> M >> T; for(int i=0;i> u >> v >> c; E[i] = Edge{u - 1, v - 1, c}; } for(int i=0;i> ts[i], ts[i]--; int res; if(T < 14){ res = min_steiner_tree(); } else { for(int i=0;i> i) & 1){ use[rest_v[i]] = true; } } res = min(res, min_spanning_tree(res)); for(int i=0;i> i) & 1){ use[rest_v[i]] = false; } } } } cout << res << endl; return 0; }