这道题要求每个节点只能经过一次，也就是结点容量为1， 要拆点， 拆成两个点， 中间连一条弧容量为1， 费用为0.
因为拆成两个点， 所以要经过原图中的这个节点就要经过拆成的这两个点， 又因为这两个点的
边的容量为1， 所以只能经过一次， 就等价于原图中的点只能经过一次。
拆点的时候要注意细节：起点和终点不用拆， 因为有两条路径， 所以起点和终点必须经过两次。
因此一开始的时候
只拆2到n-1这些点， 拆成i与n+i。起点是1， 终点是n， 源点是0， 汇点是2 * n + 1
然后后来加边的时候， 如果非源点和终点，
连接的时候是拆出来的点连原来的点， 如果是起点
和终点， 那么就是原来的点相连。最后再把源点和起点连一条弧， 容量为2， 表示有两条路径， 终点
与汇点也一样
最后求最小费用流就ok了。
#include<cstdio>
#include<vector>
#include<queue>
#include<algorithm>
#include<cstring>
#define REP(i, a, b) for(int i = (a); i < (b); i++)
using namespace std;typedef long long ll;
const int MAXN = 4123;
struct Edge
{int from, to, cap, flow, cost;Edge(int from, int to, int cap, int flow, int cost) : from(from), to(to), cap(cap), flow(flow), cost(cost) {};
};
vector<Edge> edges;
vector<int> g[MAXN];
int p[MAXN], a[MAXN], d[MAXN], vis[MAXN], n, m, s, t;void AddEdge(int from, int to, int cap, int cost)
{edges.push_back(Edge(from, to, cap, 0, cost));edges.push_back(Edge(to, from, 0, 0, -cost));g[from].push_back(edges.size() - 2);g[to].push_back(edges.size() - 1);
}bool spfa(int& flow, ll& cost)
{REP(i, 0, t + 1) d[i] = (i == s ? 0 : 1e9);memset(vis, 0, sizeof(vis));vis[s] = 1; p[s] = 0; a[s] = 1e9;queue<int> q;q.push(s);while(!q.empty()){int u = q.front(); q.pop();vis[u] = 0;REP(i, 0, g[u].size()){Edge& e = edges[g[u][i]];if(e.cap > e.flow && d[e.to] > d[u] + e.cost){d[e.to] = d[u] + e.cost;p[e.to] = g[u][i];a[e.to] = min(a[u], e.cap - e.flow);if(!vis[e.to]) { vis[e.to] = 1; q.push(e.to); }}}}if(d[t] == 1e9) return false;flow += a[t];cost += (ll)d[t] * (ll)a[t];for(int u = t; u != s; u = edges[p[u]].from){edges[p[u]].flow += a[t];edges[p[u] ^ 1].flow -= a[t];}return true;
}int mincost(ll& cost)
{int flow = 0; cost = 0;while(spfa(flow, cost));return flow;
}int main()
{while(~scanf("%d%d", &n, &m) && n){REP(i, 0, 2 * n + 1) g[i].clear();edges.clear();s = 0, t = 2 * n + 1;for(int i = 2; i <= n - 1; i++) AddEdge(i, n + i, 1, 0);while(m--){int u, v, w;scanf("%d%d%d", &u, &v, &w);if(u != 1 && u != n) AddEdge(u + n, v, 1, w);else AddEdge(u, v, 1, w);}ll ans;AddEdge(s, 1, 2, 0);AddEdge(n, t, 2, 0);mincost(ans);printf("%lld\n", ans);}return 0;
}