1 //题目上面说了“The only exception is that the first and the last city should be the same and this city is visited twice.”

  2 //我还以为是起点要使用两次，没想到题意就是全部点连接之后出入度都为1

  3

  4 //题意：有n座城市，m条带权有向边。有人想要游历所有城市，于是制定了计划：游历的路径是一个或者多个环,且所有城市都必须仅存在于一个环中。问怎样设计路线使得总路程最短？

  5 //我们可以用最大权匹配去求：

  6 //1.对于每个点u，我们拆成u和u'。u代表着出点，在二分图的左侧；u'代表着入点，在二分图的右侧。

  7 //2.如果有一条有向边u-->v，那么在二分图中，我们加一条边u-->v'，并且权值取反。

  8 //

  9 //3.利用KM()算法，求出最大权匹配，再将结果取反，即为答案。

 10 // 举个三个点的例子

 11 // p->q`->q->r`->r->p`

 12 //

 13 //问：为何KM()算法求出来的就一定是一个或多个环呢？

 14 //1.可知，题目已经说明了必定有解。那么对应的二分图必定存在完全匹配，完全匹配也必定是最大匹配。

 15 //2.我们用KM()算法求出了最大权匹配。根据性质：最大权匹配必定为最大匹配。所以，如果最大匹配是完全匹配，那么最大权匹配也是完全匹配。

 16 //3.因为最大权匹配是完全匹配。所以所求出的解必定是一个或多个环。

 17 #include<stdio.h>

 18 #include<algorithm>

 19 #include<string.h>

 20 #include<iostream>

 21 #include<queue>

 22 #include<vector>

 23 using namespace std;

 24 const int maxn=510;

 25 const int INF=0x3f3f3f3f;

 26 int n,m;

 27 int g[maxn][maxn],link[maxn],matchx[maxn],matchy[maxn];

 28 int slack[maxn],visitx[maxn],visity[maxn];

 29 int dfs(int x)

 30 {

 31     visitx[x]=1;

 32     for(int i=1;i<=n;++i)

 33     {

 34         if(visity[i]) continue;

 35         int temp=matchx[x]+matchy[i]-g[x][i];

 36         if(temp==0)

 37         {

 38             visity[i]=1;

 39             if(link[i]==-1 || dfs(link[i]))

 40             {

 41                 link[i]=x;

 42                 return 1;

 43             }

 44         }

 45         else slack[i]=min(slack[i],temp);

 46     }

 47     return 0;

 48 }

 49 int km()

 50 {

 51     memset(link,-1,sizeof(link));

 52     memset(matchy,0,sizeof(matchy));

 53     for(int i=1;i<=n;++i)

 54     {

 55         matchx[i]=-INF;

 56         for(int j=1;j<=n;++j)

 57         {

 58             matchx[i]=max(matchx[i],g[i][j]);

 59         }

 60     }

 61     for(int x=1;x<=n;++x)

 62     {

 63         for(int i=1;i<=n;++i)

 64             slack[i]=INF;

 65         while(1)

 66         {

 67             memset(visitx,0,sizeof(visitx));

 68             memset(visity,0,sizeof(visity));

 69             if(dfs(x)) break;

 70             int d=INF;

 71             for(int i=1;i<=n;++i)

 72                 if(!visity[i])

 73                     d=min(d,slack[i]);

 74             for(int i=1;i<=n;++i)

 75             {

 76                 if(visitx[i])

 77                     matchx[i]-=d;

 78             }

 79             for(int i=1;i<=n;++i)

 80             {

 81                 if(visity[i]) matchy[i]+=d;

 82                 else slack[i]-=d;

 83             }

 84         }

 85     }

 86     int ans=0;

 87     for(int i=1;i<=n;++i)

 88     {

 89         if(link[i]!=-1)

 90             ans+=g[link[i]][i];

 91     }

 92     return ans;

 93 }

 94 int main()

 95 {

 96     int t;

 97     scanf("%d",&t);

 98     while(t--)

 99     {

100         scanf("%d%d",&n,&m);

101         memset(g,0,sizeof(g));

102         for(int i=1;i<=n;++i)

103         {

104             for(int j=1;j<=n;++j)

105             {

106                 g[i][j]=-INF;

107             }

108         }

109         while(m--)

110         {

111             int u,v,w;

112             scanf("%d%d%d",&u,&v,&w);

113             g[u][v]=max(-w,g[u][v]);

114         }

115         printf("%d\n",-km());

116     }

117     return 0;

118 }