先说我的问题，代码在最后。

我尝试把每一条边权都加上一个较大的值，强行把连边的边权变成正数，未连边的值为零。然后 wa 在了最后一个点。最后一组数据左侧的 498 连接了右侧的 496，这显然是不对的，这两个点之间甚至没有边。

接着我把未连边的值变成 $-INF = -1e18$ 就可以了，那这样我强行把边权变正就没有意义了。

带有负权边的完美匹配不能把权值变正再做吗？

接着是我的 AC 代码。

// created on Lucian Xu's Laptop

#include <bits/stdc++.h>

// using namespace std;

typedef unsigned int UI;
typedef unsigned long long ULL;
typedef long long LL;
typedef unsigned long long ULL;
typedef std::pair<int, int> PII;
typedef std::pair<int, LL> PIL;
typedef std::pair<LL, int> PLI;
typedef std::pair<LL, LL> PLL;
typedef std::vector<int> vi;
typedef std::vector<vi> vvi;
typedef std::vector<LL> vl;
typedef std::vector<vl> vvl;
typedef std::vector<PII> vpi;

#define typet typename T
#define typeu typename U
#define types typename... Ts
#define tempt template <typet>
#define tempu template <typeu>
#define temps template <types>
#define tandu template <typet, typeu>

#define rep(i, l, r) for (auto i = (l); i <= (r); i++)
#define per(i, r, l) for (auto i = (r); i >= (l); i--)
#define ff first
#define ss second
#define makepair make_pair
#define pushback push_back
#define endl '\n'
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) \
    do {           \
    } while (false)
#endif

constexpr int N = 2e5 + 10;
constexpr int mod = 998244353;
constexpr int inf = 0x3f3f3f3f;
constexpr LL INF = 1e18;
const double pi = std::acos(-1);
const double eps = 1e-6;

constexpr int lowbit(int x) { return x & -x; }
constexpr int add(int x, int y) { return x + y < mod ? x + y : x - mod + y; }
constexpr int sub(int x, int y) { return x < y ? mod + x - y : x - y; }
constexpr int mul(LL x, int y) { return x * y % mod; }
constexpr void Add(int& x, int y) { x = add(x, y); }
constexpr void Sub(int& x, int y) { x = sub(x, y); }
constexpr void Mul(int& x, int y) { x = mul(x, y); }
constexpr int pow(int x, int y, int z = 1) {
    for (; y; y /= 2) {
        if (y & 1) Mul(z, x);
        Mul(x, x);
    }
    return z;
}
temps constexpr int add(Ts... x) {
    int y = 0;
    (..., Add(y, x));
    return y;
}
temps constexpr int mul(Ts... x) {
    int y = 1;
    (..., Mul(y, x));
    return y;
}

tempt bool Max(T& x, const T& y) { return x < y ? x = y, true : false; }
tempt bool Min(T& x, const T& y) { return x > y ? x = y, true : false; }

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);

    int n, m;
    std::cin >> n >> m;
    vvl e(n + 1, vl(n + 1, -INF));
    for (int i = 1; i <= m; i++) {
        int u, v, w;
        std::cin >> u >> v >> w;
        // debug(u, v, w + 20000000);
        Max(e[u][v], (LL) w + inf);
        // Max(e[u][v], w);
    }
    vi mchl(n + 1), mchr(n + 1);
    auto KM = [&](vvl e, vi& match, int n) -> LL {
        vl la(n + 1), lb(n + 1), pp(n + 1), vx(n + 1);
        std::vector<int> va(n + 1), vb(n + 1);
        LL delta;
        auto bfs = [&](int x) -> void {
            int a, y = 0, y1 = 0;
            std::fill(all(pp), 0);
            std::fill(all(vx), INF);
            match[y] = x;
            do {
                a = match[y], delta = INF, vb[y] = 1;
                for (int b = 1; b <= n; b++) {
                    if (!vb[b]) {
                        if (vx[b] > la[a] + lb[b] - 1ll * e[a][b]) {
                            vx[b] = la[a] + lb[b] - 1ll * e[a][b];
                            pp[b] = y;
                        }
                        if (vx[b] < delta) {
                            delta = vx[b];
                            y1 = b;
                        }
                    }
                }
                for (int b = 0; b <= n; b++) {
                    if (vb[b]) {
                        la[match[b]] -= delta;
                        lb[b] += delta;
                    } else
                        vx[b] -= delta;
                }
                y = y1;
            } while (match[y]);
            while (y) {
                match[y] = match[pp[y]];
                y = pp[y];
            }
        };
        for (int i = 1; i <= n; i++) {
            std::fill(all(vb), 0);
            bfs(i);
        }
        LL ans = 0;
        for (int i = 1; i <= n; i++) ans += e[match[i]][i];
        return ans;
    };
    LL ans = KM(e, mchl, n) - 1ll * inf * n;
    std::cout << ans << endl;
    for (int i = 1; i <= n; i++) {
        std::cout << mchl[i] << ' ';
    }


    return 0;
}