这个题一眼看上去不会
然后有人说是网络流
然后我就想怎么建图啊，然后不会(是本蒟蒻太垃圾了)，肯定有网络流解法
然后去群里问了gdut的巨巨，他说他队友爆搜+剪枝过了（我也是非常的叹服）
然后我也写了一个2^50的搜索剪枝，居然真过了（不知道是数据弱还是大力出奇迹）
#include <cstdio>
#include <iostream>
#include <ctime>
#include <vector>
#include <cmath>
#include <map>
#include <queue>
#include <algorithm>
#include <cstring>
using namespace std;
typedef long long LL;
const int N=1e5+;
const int INF=0x3f3f3f3f;
const int mod=1e9+;
vector<int>g[],v[],op[];
int belong[],ret,n,m;
void dfs(int pos,int c,int t1,int t2){
if(t1>n-||t2>n-)return;
if(c>=ret)return;
if(n==pos){
if(t2+>n-)return;
for(int i=;i<g[n].size();++i){
if(op[n][i]==&&belong[g[n][i]]==)c+=v[n][i];
}
ret=min(ret,c);
return;
}
belong[pos]=;
int tmp=;
for(int i=;i<g[pos].size();++i){
if(op[pos][i]==&&belong[g[pos][i]]==)tmp+=v[pos][i];
}
dfs(pos+,c+tmp,t1+,t2);
belong[pos]=;
for(int i=;i<g[pos].size();++i){
if(op[pos][i]==&&belong[g[pos][i]]==)c+=v[pos][i];
}
dfs(pos+,c,t1,t2+);
}
int main()
{
while(~scanf("%d%d",&n,&m)){
for(int i=;i<=n;++i){
v[i].clear();
g[i].clear();
op[i].clear();
}
for(int i=;i<=m;++i){
int k1,k2,k3;
scanf("%d%d%d",&k1,&k2,&k3);
if(k1>k2){
v[k1].push_back(k3);
g[k1].push_back(k2);
op[k1].push_back();
}
else{
v[k2].push_back(k3);
g[k2].push_back(k1);
op[k2].push_back();
}
}
ret=INF;
belong[]=;
dfs(,,,);
printf("%d\n",ret);
}
return ;
}