1 #include<cstdio>  2 #include<cstring>  3 #include<cstdlib>  4 #include<cmath>  5 #include<map>  6 #include<stack>  7 #include<queue>  8 #include<vector>  9 #include<iostream> 10 #include<algorithm> 11 #define mt(a,b) memset(a,b,sizeof(a)) 12 using namespace std; 13 const int inf=0x3f3f3f3f; 14 class MaxFlowMinCost{///最小费用最大流 o(ME) 15     typedef int typef;///流量的类型 16     typedef int typec;///费用的类型 17     static const int ME=100010;///边的个数 18     static const int MV=1010;///点的个数 19     queue<int> q; 20     int cur[MV],pre[MV]; 21     bool used[MV],sign[MV]; 22     typef flow; 23     typec cost,dist[MV]; 24     bool spfa(int s,int t) { 25         mt(used,0); 26         mt(sign,0); 27         mt(dist,0); 28         used[s]=sign[s]=true; 29         while(!q.empty()) q.pop(); 30         q.push(s); 31         while(!q.empty()) { 32             int u=q.front(); 33             q.pop(); 34             used[u]=false; 35             for(int i=g.head[u]; ~i; i=g.e[i].next) { 36                 if(g.e[i].flow<1) continue; 37                 int v=g.e[i].v; 38                 typec c=g.e[i].cost; 39                 if(!sign[v]||dist[v]>dist[u]+c) { 40                     dist[v]=dist[u]+c; 41                     sign[v]=true; 42                     pre[v]=u; 43                     cur[v]=i; 44                     if(used[v]) continue; 45                     used[v]=true; 46                     q.push(v); 47                 } 48             } 49         } 50         return sign[t]; 51     } 52     struct G{ 53         struct E{ 54             int v,next; 55             typef flow; 56             typec cost; 57         }e[ME]; 58         int le,head[MV]; 59         void init(){ 60             le=0; 61             mt(head,-1); 62         } 63         void add(int u,int v,typef flow,typec cost){ 64             e[le].v=v; 65             e[le].flow=flow; 66             e[le].cost=cost; 67             e[le].next=head[u]; 68             head[u]=le++; 69         } 70     }g; 71 public: 72     void init(){ 73         g.init(); 74     } 75     void add(int u,int v,typef flow,typec cost){ 76         g.add(u,v,flow,cost); 77         g.add(v,u,0,-cost); 78     } 79     void solve(int s,int t) { 80         flow=cost=0; 81         while(spfa(s,t)) { 82             int temp=t; 83             typef now=inf; 84             while(temp!=s) { 85                 now=min(now,g.e[cur[temp]].flow); 86                 temp=pre[temp]; 87             } 88             flow+=now; 89             temp=t; 90             while(temp!=s) { 91                 int id=cur[temp]; 92                 cost+=now*g.e[id].cost; 93                 g.e[id].flow-=now; 94                 g.e[id^1].flow+=now; 95                 temp=pre[temp]; 96             } 97         } 98     } 99     typef getflow(){100         return flow;101     }102     typec getcost(){103         return cost;104     }105 }graph;106 int n,m;107 int main()108 {109     while(~scanf("%d%d",&n,&m))110     {111         graph.init();112         int s=0;113         int t=n+1;114         graph.add(s,1,2,0);115         graph.add(n,t,2,0);116         for(int i=0;i<m;i++)117         {118             int a,b,c;119             scanf("%d%d%d",&a,&b,&c);120             graph.add(a,b,1,c);121             graph.add(b,a,1,c);122         }123         graph.solve(s,t);124         int ans=graph.getcost();125         printf("%d\n",ans);126     }127     return 0;128 }