Cyclic Tour

6 9
1 2 5
2 3 5
3 1 10
3 4 12
4 1 8
4 6 11
5 4 7
5 6 9
6 5 4
6 5
1 2 1
2 3 1
3 4 1
4 5 1
5 6 1

42
-1

Hint
 In the first sample, there are two cycles, (1->2->3->1) and (6->5->4->6) whose length is 20 + 22 = 42. 
 

#include<stdio.h>
#include<string.h>
#include<queue>
using namespace std;
const int MAXN = 10010;
const int MAXM = 100100;
const int INF = 1<<30;
struct EDG{
    int to,next,cap,flow;
    int cost;  //每条边的单位价格
}edg[MAXM];
int head[MAXN],eid;
int pre[MAXN], cost[MAXN]  ; //点0~(n-1)

void init(){
    eid=0;
    memset(head,-1,sizeof(head));
}
void addEdg(int u,int v,int cap,int cst){
    edg[eid].to=v; edg[eid].next=head[u]; edg[eid].cost = cst;
    edg[eid].cap=cap; edg[eid].flow=0; head[u]=eid++;

    edg[eid].to=u; edg[eid].next=head[v]; edg[eid].cost = -cst;
    edg[eid].cap=0; edg[eid].flow=0; head[v]=eid++;
}

bool inq[MAXN];
bool spfa(int sNode,int eNode,int n){
    queue<int>q;
    for(int i=0; i<n; i++){
        inq[i]=false; cost[i]= INF;
    }
    cost[sNode]=0; inq[sNode]=1; pre[sNode]=-1;
    q.push(sNode);
    while(!q.empty()){
        int u=q.front(); q.pop();
        inq[u]=0;
        for(int i=head[u]; i!=-1; i=edg[i].next){
            int v=edg[i].to;
            if(edg[i].cap-edg[i].flow>0 && cost[v]>cost[u]+edg[i].cost){ //在满足可增流的情况下，最小花费
                cost[v] = cost[u]+edg[i].cost;
                pre[v]=i;   //记录路径上的边
                if(!inq[v])
                    q.push(v),inq[v]=1;
            }
        }
    }
    return cost[eNode]!=INF;    //推断有没有增广路
}
//反回的是最大流，最小花费为minCost
int minCost_maxFlow(int sNode,int eNode ,int& minCost,int n){
    int ans=0;
    while(spfa(sNode,eNode,n)){
        ans++;
        for(int i=pre[eNode]; i!=-1; i=pre[edg[i^1].to]){
            edg[i].flow+=1; edg[i^1].flow-=1;
            minCost+=edg[i].cost;
        }
    }
    return ans;
}
void scanf(int &ans){
    char ch;
    while(ch=getchar()){
        if(ch>='0'&&ch<='9')
            break;
    }
    ans=ch-'0';
    while(ch=getchar()){
        if(ch<'0'||ch>'9')
            break;
        ans=ans*10+ch-'0';
    }
}
int  mapt[1005][1005];
int main(){
    int n,m , u, v, d ;
    while(scanf("%d%d",&n,&m)>0){
        init();
        int s=0, t=2*n+1;

        for(int i=1; i<=n; i++){
            addEdg(s , i , 1 , 0);
            addEdg(i+n , t , 1 , 0);
            for(int j=1; j<=n; j++)
                mapt[i][j]=INF;
        }
        while(m--){
            scanf(u); scanf(v); scanf(d);
            if(mapt[u][v]>d)
                mapt[u][v]=d;
        }
        for( u=1; u<=n; u++)
            for(v=1; v<=n; v++)
            if(mapt[u][v]!=INF)
                addEdg(u,v+n,1,mapt[u][v]);

        int mincost=0;
       n-= minCost_maxFlow(s , t , mincost , t+1);
        if(n==0)
            printf("%d\n",mincost);
        else
            printf("-1\n");
    }
}