题目：

解题思路：

建图：把除了源点和汇点的其它路口拆成两个点，入点和出点，两点之间边最大流量为1，费用为0，其他流量为inf，费用为长度：

源程序：

#include
    
     #include
     
      #define inf 1e9#define min(a,b) a>b?b:ausing namespace std;struct node{    int x,y,c,f,next;}e[100001];int last[5001],d[5001],v[5001],pre[5001],ans,sum,n,m,s,t,cnt=-1;void add(int u,int v,int c,int f){    e[++cnt].x=u;e[cnt].y=v;e[cnt].c=c;e[cnt].f=f;e[cnt].next=last[u];last[u]=cnt;    e[++cnt].x=v;e[cnt].y=u;e[cnt].c=0;e[cnt].f=-f;e[cnt].next=last[v];last[v]=cnt;} bool spfa(){    for (int i=1;i<=2*n+2;i++) d[i]=inf,v[i]=0;    queue
      
        q;    q.push(s);d[s]=0;v[s]=1;    while (q.size())    {        int u=q.front(); q.pop(); v[u]=0;        for (int i=last[u];~i;i=e[i].next)        if (e[i].c&&d[e[i].y]>d[u]+e[i].f)         {            d[e[i].y]=d[u]+e[i].f;            pre[e[i].y]=i;            if (!v[e[i].y])            {                v[e[i].y]=1;                q.push(e[i].y);             }        }     }    return d[t]!=inf;}void mcf(){    int minn=inf,p=t;    while(~pre[p])    {        minn=min(e[pre[p]].c,minn);        p=e[pre[p]].x;    }    ans+=minn;sum+=d[t]*minn;    p=t;    while(~pre[p])    {        e[pre[p]].c-=minn;        e[pre[p]^1].c+=minn;        p=e[pre[p]].x;    }    return;}int main(){    for (int i=0;i<=500;i++) last[i]=pre[i]=-1;    scanf("%d%d",&n,&m);    s=2*n+1;t=2*n+2;    for (int i=1;i<=m;i++)    {        int a,b,c;        scanf("%d%d%d",&a,&b,&c);        if (a==1&&b!=n) add(s,b*2-1,1,c);        else if (a!=1&&b==n) add(a*2,t,1,c);        else if (a==1&&b==n) add(s,t,1,c);        else add(a*2,b*2-1,1,c);    }    for (int i=2;i