求调 54pts

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = LLONG_MAX;
int n, m, x, y, matched[505], bef[505];
ll dis[505][505], ex[505], ey[505], slack[505], w;
bool vis[505];
void match(int now) {
	int x, y = 0, ty = 0;
	matched[y] = now;
	while (true) {
		x = matched[y];
		ll d = INF;
		vis[y] = true;
		for (int i = 1; i <= n; i++) {
			if (vis[i]) continue;
			if (slack[i] > ex[x] + ey[i] - dis[x][i]) {
				slack[i] = ex[x] + ey[i] - dis[x][i];
				bef[i] = y;
			}
			if (slack[i] < d) {
				d = slack[i];
				ty = i;
			}
		}
		for (int i = 0; i <= n; i++) {
			if (vis[i]) {
				ex[matched[i]] -= d;
				ey[i] += d;
			} else {
				slack[i] -= d;
			}
		}
		y = ty;
		if (!matched[y]) break;
	}
	while (y) {
		matched[y] = matched[bef[y]];
		y = bef[y];
	}
}
ll KM() {
	for (int i = 1; i <= n; i++) {
		memset(vis, false, sizeof vis);
		for (int j = 1; j <= n; j++) slack[j] = INF;
        memset(bef, 0, sizeof bef);
		match(i);
	}
	ll res = 0;
	for (int i = 1; i <= n; i++)
		if (matched[i])
			res += dis[matched[i]][i];
	return res;
}
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) {
        ey[i] = -INF;
        for (int j = 1; j <= n; j++) dis[i][j] = -INF;
    }
    for (int i = 1; i <= m; i++) {
        scanf("%d%d%lld", &x, &y, &w);
        dis[x][y] = max(dis[x][y], w);
        ex[x] = max(ex[x], dis[x][y]);
    }
    printf("%lld\n", KM());
    for (int i = 1; i <= n; i++) printf("%d ", matched[i]);
    return 0;
}