問題文

整数 $T$ と $N$ 頂点 $M$ 辺からなる重み付きグラフが与えられます。
このグラフには同一の $2$ 頂点間を結ぶ辺は $1$ つまでしか存在しません。またこのグラフには両端の頂点が同じであるような辺は存在しません。

$T$ は $0$ あるいは $1$ のどちらかの値です。

• $T=0$ のとき

  与えられるグラフは無向グラフです。 $i$ 番目の辺は頂点 $u_i$ と $v_i$ を重み $w_i$ で双方向に接続しています。

• $T=1$ のとき

  与えられるグラフは有向グラフです。 $i$ 番目の辺は頂点 $u_i$ から $v_i$ に重み $w_i$ で接続しています。

与えられるグラフに含まれる最小の閉路の大きさを求めてください。閉路の大きさとは、含まれる辺の重みの和です。 閉路が存在しない場合は-1を出力してください。

入力

$T$
$N\ M$
$u_1\ v_1\ w_1$
$\vdots$
$u_M\ v_M\ w_M$

• 与えられる入力は全て整数
• $0 \le T \le 1$
• $1 \le N \le 2000$
• $0 \le M \le \min( 2000, N(N-1)/2) $
• $1 \le u_i \le N$
• $1 \le v_i \le N$
• $1 \le w_i \le 10^9$
• $u_i \neq v_i $
• $(u_i,v_i) \neq (u_j,v_j) \ (i \neq j) $
• $(u_i,v_i) \neq (v_j,u_j) \ (i \neq j) $

出力

与えられるグラフに含まれる最小の閉路の大きさを求めてください。閉路が存在しない場合は-1を出力してください。

最後に改行してください。

サンプル

0
4 5
1 2 1
2 3 2
2 4 3
1 3 4
4 1 5

7

1
4 5
1 2 1
2 3 2
2 4 3
1 3 4
4 1 5

9

0
3 1
1 2 1

-1