AT_abc338_f [ABC338F] Negative Traveling Salesman

有一个包含 $N$ 个顶点和 $M$ 条边的带权有向简单图。顶点编号为 $1$ 到 $N$，第 $i$ 条边是从顶点 $U_i$ 指向顶点 $V_i$，权值为 $W_i$。这里，权值可以为负数，但图中不存在负权回路。 请判断是否存在一条经过所有顶点至少一次的“行走”（Walk），如果存在，求经过的边权之和的最小值。注意，如果同一条边经过多次，其权值会被多次累加。 所谓“经过所有顶点至少一次的行走”是指，存在一个顶点序列 $v_1,v_2,\dots,v_k$，满足以下条件： - 对于所有 $i\ (1\leq i\leq k-1)$，存在一条从 $v_i$ 到 $v_{i+1}$ 的有向边； - 对于所有 $j\ (1\leq j\leq N)$，存在至少一个 $i\ (1\leq i\leq k)$ 使得 $v_i = j$。

输入以如下格式从标准输入读入。 > $N$ $M$ > $U_1$ $V_1$ $W_1$ > $U_2$ $V_2$ $W_2$ > $\vdots$ > $U_M$ $V_M$ $W_M$

如果存在经过所有顶点至少一次的行走，输出经过的边权之和的最小值；否则输出 `No`。

## 限制条件 - $2 \leq N \leq 20$ - $1 \leq M \leq N(N-1)$ - $1 \leq U_i, V_i \leq N$ - $U_i \neq V_i$ - $(U_i, V_i) \neq (U_j, V_j)\ (i \neq j)$ - $-10^6 \leq W_i \leq 10^6$ - 给定的图中不存在负权回路 - 所有输入均为整数 ## 样例解释 1 按顶点 $2\rightarrow 1\rightarrow 2\rightarrow 3$ 的顺序行走，可以经过所有顶点一次以上，经过的边权之和为 $(-3)+5+(-4)=-2$，这是最小值。 ## 样例解释 2 不存在经过所有顶点至少一次的行走。 由 ChatGPT 4.1 翻译