AT_abc338_f [ABC338F] Negative Traveling Salesman

[problemUrl]: https://atcoder.jp/contests/abc338/tasks/abc338_f $ N $ 頂点 $ M $ 辺の重み付き単純有向グラフがあります。 頂点には $ 1 $ から $ N $ までの番号が付けられていて、$ i $ 本目の辺は頂点 $ U_i $ から頂点 $ V_i $ に伸びる重み $ W_i $ の辺です。 ここで、重みは負の値を取ることもありますが、負閉路は存在しません。 全ての頂点を一度以上通るようなウォークが存在するかどうか判定し、存在するならば通る辺の重みの総和の最小値を求めてください。 ただし、同じ辺を複数回通る場合、その辺の重みは通った回数分加算されるものとします。 なお、「全ての頂点を一度以上通るようなウォーク」とは、頂点の列 $ 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) $ について、$ v_i=j $ を満たす $ i\ (1\leq\ i\leq\ k) $ が存在する

入力は以下の形式で標準入力から与えられる。 > $ 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 $ - 与えられるグラフに負閉路は存在しない - 入力は全て整数 ### Sample Explanation 1 頂点 $ 2\rightarrow\ 1\rightarrow\ 2\rightarrow\ 3 $ の順に辿ると、全ての頂点を一度以上通ることができ、通る辺の重みの総和は $ (-3)+5+(-4)=-2 $ になります。 これが最小です。 ### Sample Explanation 2 全ての頂点を一度以上通るようなウォークは存在しません。