#include <cstdio> 
#include <queue>
#include <cstring>
#define N 200
#define M 500000
#define QWQ cout << "QWQ" << endl;
const int INF = 1000000000;
using namespace std;
int n, m, dis[N + 10][N + 10], s, t, k;
int min(int x, int y) {return ((x < y) ? (x) : (y));}
int max(int x, int y) {return ((x > y) ? (x) : (y));}
void ready() {
	for(int p = 1; p <= 200; p++)
		for(int i = 1; i <= 200; i++)
			if(p != i) dis[p][i] = INF;
}
void init() {
	ready();
	scanf("%d%d%d", &n, &m, &k), n++, s = n * 2 + 1, t = n * 2 + 2;
	for(int p = 1, x, y, z; p <= m; p++) {
		scanf("%d%d%d", &x, &y, &z), x++, y++;
		dis[x][y] = dis[y][x] = min(dis[x][y], z);
	}
}
void floyd() {
	for(int p = 1; p <= n; p++)
		for(int i = 1; i <= n; i++)
			for(int j = 1; j <= n; j++)
				if(p < i || p < j)
					dis[i][j] = min(dis[i][j], dis[i][p] + dis[p][j]);
}
struct node {
	int to, val, ro, next;
} gra[M * 2 + 10];
int head[M * 2 + 10], tot = 1;
void link(int x, int y, int z, int R) {
	gra[++tot].to = y, gra[tot].val = z, gra[tot].ro = R, gra[tot].next = head[x], head[x] = tot;
	gra[++tot].to = x, gra[tot].val = -z, gra[tot].ro = 0, gra[tot].next = head[y], head[y] = tot;
}
void connect() {
	link(s, 1, 0, k);
	for(int p = 1; p <= n; p++) {
		if(p != 1) link(s, p, 0, 1);
		link(p + n, t, 0, 1);
	}
	for(int p = 1; p <= n; p++)
		for(int i = p + 1; i <= n; i++)
			if(dis[p][i] != INF)
				link(p, i + n, dis[p][i], INF);
}
int d[N + 10], pre[N + 10], over[N + 10];
bool vis[N + 10];
int maxn = 0, minn = 0;
void mcmf() {
	while(1) {
		queue <int> que;
	    que.push(s);
	    memset(d, 0x7f, sizeof(d));
	    memset(vis, 0, sizeof(vis));
	    int INF = d[0];
	    vis[s] = 1, d[s] = 0, over[s] = 0x7f7f7f7f;
	    while(!que.empty()) {
	        int fr = que.front(); que.pop();
	        vis[fr] = 0;
	        for(int p = head[fr]; p; p = gra[p].next) {
	            int v = gra[p].to, w = gra[p].val;
	            if(gra[p].ro && d[v] > d[fr] + w) {
	                d[v] = d[fr] + w;
	                pre[v] = p, over[v] = min(over[fr], gra[p].ro);
	                if(!vis[v]) {
	                    vis[v] = 1;
	                    que.push(v);
	                }
	            }
	        }
	    }
	    if(d[t] == INF) break;
		int now = t;
	    while(now != s) {
	        int pr = pre[now];
	        gra[pr].ro -= over[t];
	        gra[pr ^ 1].ro += over[t];
	        now = gra[pr ^ 1].to;
	    }
	    maxn += over[t];
	    minn += over[t] * d[t];
	}
}
signed main() {
	init(), floyd(), connect();
	mcmf();
    printf("%d", minn);
}

我看题解里面的好多都是这样写的费用流，但是为啥我 70pts 3 点 T 啊/kk
求助 awa