题意：找两条完全不相交不重复的路使得权值和最小。
思路：比赛的时候时间都卡在D题了，没有仔细的想这题，其实还是很简单的，将每个点拆开，连一条容量为1，费用为0的边，起点和终点容量为2，两点之间有边就加一条容量为1，费用为权值的边，这样跑一边费用流就可以了。
#pragma comment(linker, "/STACK:1000000000")
#include <bits/stdc++.h>
#define LL long long
#define INF 0x3f3f3f3f
#define IN freopen("in.txt","r",stdin);
#define OUT freopen("out.txt","w",stdout);
using namespace std;
#define MAXN 9999
#define V 2005
#define E 30005
int vis[V];
int dist[V];
int pre[V]; struct Edge{
int u,v,c,cost,next;
}edge[E];
int head[V],cnt; void init(){
cnt=;
memset(head,-,sizeof(head));
}
void addedge(int u,int v,int c,int cost)
{
edge[cnt].u=u;edge[cnt].v=v;edge[cnt].cost=cost;
edge[cnt].c=c;edge[cnt].next=head[u];head[u]=cnt++; edge[cnt].u=v;edge[cnt].v=u;edge[cnt].cost=-cost;
edge[cnt].c=;edge[cnt].next=head[v];head[v]=cnt++;
} bool spfa(int begin,int end){
int u,v;
queue<int> q;
for(int i=;i<=end+;i++){
pre[i] = -;
vis[i] = ;
dist[i] = INF;
}
vis[begin]=;
dist[begin]=;
q.push(begin);
while(!q.empty()){
u=q.front();
q.pop();
vis[u]=;
for(int i=head[u];i!=-;i=edge[i].next){
if(edge[i].c>){
v=edge[i].v;
if(dist[v]>dist[u]+edge[i].cost){
dist[v]=dist[u]+edge[i].cost;
pre[v]=i;
if(!vis[v]){
vis[v]=true;
q.push(v);
}
}
}
}
}
return dist[end] != INF;
} int MCMF(int begin,int end){
int ans=,flow;
int flow_sum=;
while(spfa(begin,end)){
flow=INF;
for(int i=pre[end];i!=-;i=pre[edge[i].u])
if(edge[i].c<flow)
flow=edge[i].c;
for(int i=pre[end];i!=-;i=pre[edge[i].u]){
edge[i].c-=flow;
edge[i^].c+=flow;
}
ans+=dist[end];
flow_sum += flow;
}
//cout << flow_sum << endl;
return ans;
} int main()
{
//IN;
int n, m, x, y, z;
while(~scanf("%d%d", &n, &m)){
init();
int s = , t = * n;
for(int i = ; i < n; i++){
addedge(i, i + n, , );
}
addedge(, n + , , );
addedge(n, n << , , );
for(int i = ; i <= m; i++){
scanf("%d%d%d", &x, &y, &z);
addedge(x + n, y, , z);
}
int ans = MCMF(s, t);
printf("%d\n", ans);
}
return ;
}