所有路径的费用之和就是总的最小费用。
   
    */
   
    void AddEdge（int u,int v,int p,int f）
   
    {
   
    e[size]=Edge（v,p,f,head[u]）；
   
    head[u]=size++;
   
    e[size]=Edge（u,-p,0,head[v]）；
   
    head[v]=size++;
   
    }
   
    bool SPFA（int s,int t,int n）
   
    {
   
    int f,u,v,i;
   
    queue<int> que;
   
    while（ !que.empty（）） que.pop（）；
   
    memset（vis,0,sizeof（vis））；
   
    memset（dist,0x7f,sizeof（dist））；
   
    memset（pre,-1,sizeof（pre））；
   
    que.push（s）， vis[s]=true, dist[s]=0;
   
    while（ !que.empty（））{
   
    u=que.front（）；
   
    que.pop（）， vis[u]=false;
   
    for（ i=head[u];i!=-1;i=e[i].next）{
   
    v=e[i].v;
   
    if（ e[i].f&&dist[v]>dist[u]+e[i].p）{
   
    dist[v]=dist[u]+e[i].p;
   
    pre[v]=u;
   
    cur[v]=i;
   
    /* pre,cur数组记录路径*/
   
    if（ !vis[v]）{
   
    que.push（v）；
   
    vis[v]=1;
   
    }
   
    }
   
    }
   
    }
   
    if（pre[t]==-1） return false;
   
    return true;
   
    }
   
    void Update（int u）  //在找到的 最小费用增广路径上修改流量
   
    {
   
    if（pre[u]==-1） return ;
   
    if（ mimf>e[cur[u]].f） mimf=e[cur[u]].f;
   
    Update（pre[u]）；
   
    e[cur[u]].f-=mimf;
   
    e[cur[u]^1].f+=mimf;
   
    }
   
    int main（）
   
    {
   
    int n,m,a,b,c,ans;
   
    scanf（“%d%d”,&n,&m）；
   
    memset（head,-1,sizeof（head））；
   
    size=0;
   
    while（ m--）{
   
    scanf（“%d%d%d”,&a,&b,&c）；
   
    AddEdge（a,b,c,1）；   //因为是无向图，将两条边。
   
    AddEdge（b,a,c,1）；
   
    }
   
    AddEdge（0,1,0,2）；
   
    AddEdge（n,n+1,0,2）；
   
    ans=0;
   
    while（ SPFA（0,n+1,n））{
   
    mimf=INF;
   
    Update（n+1）；
   
    ans+=mimf*dist[n+1];
   
    }
   
    printf（“%d\n”,ans）；
   
    return 0;
   
    }