思路：挺裸的费用流，拆拆点就好啦。

#include
     
      #define LL long long#define fi first#define se second#define mk make_pair#define PII pair
      
       #define y1 skldjfskldjg#define y2 skldfjsklejgusing namespace std;const int N = 500 + 7;const int M = 5e5 + 7;const int inf = 0x3f3f3f3f;const LL INF = 0x3f3f3f3f3f3f3f3f;const int mod = 1000000007;int n, m, edgenum, S, T, head[N], dist[N], pre[N];bool vis[N];struct Edge {    int from, to, cap, flow, cost, next;} edge[M];void init() {    edgenum = 0;    memset(head, -1, sizeof(head));}void addEdge(int u, int v, int w, int c) {    Edge E1 = {u, v, w, 0, c, head[u]};    edge[edgenum] = E1;    head[u] = edgenum++;    Edge E2 = {v, u, 0, 0, -c, head[v]};    edge[edgenum] = E2;    head[v] = edgenum++;}bool SPFA(int s, int t) {    queue
       
         Q;    memset(dist, INF, sizeof(dist));    memset(vis, false, sizeof(vis));    memset(pre, -1, sizeof(pre));    dist[s] = 0; vis[s] = true; Q.push(s);    while(!Q.empty()) {        int u = Q.front(); Q.pop(); vis[u] = false;        for(int i = head[u]; i != -1; i = edge[i].next) {            Edge E = edge[i];            if(dist[E.to] > dist[u] + E.cost && E.cap > E.flow) {                dist[E.to] = dist[u] + E.cost;                pre[E.to] = i;                if(!vis[E.to]) {                    vis[E.to] = true;                    Q.push(E.to);                }            }        }    }    return pre[t] != -1;}void MCMF(int s, int t, int &cost, int &flow) {    flow = 0; cost = 0;    while(SPFA(s, t)) {        int Min = INF;        for(int i = pre[t]; i != -1; i = pre[edge[i^1].to]) {            Edge E = edge[i];            Min = min(Min, E.cap - E.flow);        }        for(int i = pre[t]; i != -1; i = pre[edge[i^1].to]) {            edge[i].flow += Min;            edge[i^1].flow -= Min;            cost += edge[i].cost * Min;        }        flow += Min;    }}int main() {    init();    scanf("%d%d", &n, &m);    S = 1, T = 2 * n;    for(int i = 2; i < n; i++) addEdge(i, i + n, 1, 0);    addEdge(1, 1 + n, inf, 0); addEdge(n, n + n, inf, 0);    for(int i = 1; i <= m; i++) {        int u, v, c;        scanf("%d%d%d", &u, &v, &c);        addEdge(u + n, v, 1, c);    }    int cost, flow;    MCMF(S, T, cost, flow);    printf("%d %d\n", flow, cost);    return 0;}/**/