负权旅行商问题

题目描述

有一个带权的简单有向图，包含 $N$ 个顶点和 $M$ 条边。 顶点编号为 $1$ 到 $N$，第 $i$ 条边从顶点 $U_i$ 指向顶点 $V_i$，权重为 $W_i$。 权重可以为负数，但图中不包含负环。

请判断是否存在一条经过每个顶点至少一次的游走（walk）。如果存在，求出所经过边的总权重的最小值。 如果同一条边被经过多次，则每次经过都累加该边的权重。

这里，「经过每个顶点至少一次的游走」是指满足以下两个条件的顶点序列 $v_1, v_2, \dots, v_k$：

• 对所有 $i\ (1 \le i \le k-1)$，存在一条从顶点 $v_i$ 指向顶点 $v_{i+1}$ 的边。
• 对所有 $j\ (1 \le j \le N)$，存在 $i\ (1 \le i \le 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。

样例

3 4
1 2 5
2 1 -3
2 3 -4
3 1 100

-2

按顶点顺序 $2 \rightarrow 1 \rightarrow 2 \rightarrow 3$ 前进，可以经过所有顶点至少一次，所经过边的总权重为 $(-3)+5+(-4)=-2$。 这是最小值。

3 2
1 2 0
2 1 0

No

不存在经过所有顶点至少一次的游走。

5 9
1 2 -246288
4 5 -222742
3 1 246288
3 4 947824
5 2 -178721
4 3 -947824
5 4 756570
2 5 707902
5 1 36781

-449429

数据范围

• $2 \le N \le 20$
• $1 \le M \le N(N-1)$
• $1 \le U_i, V_i \le N$
• $U_i \neq V_i$
• 对 $i \neq j$，$(U_i, V_i) \neq (U_j, V_j)$
• $-10^6 \le W_i \le 10^6$
• 给定的图不包含负环。
• 所有输入值均为整数。