ようやくmediumを解き終えた． しかし，残り時間があとわずかしかない． 急いでhardの問題文を読んだところ，どうやら巡回セールスマン問題のようだ． しかし，頂点数がとても大きく，普通の解法では解けそうにない． きっと，なにか条件を読み落としたのだろう． もう一度読みなおす時間もないし，各頂点から出て行く辺のうち最もコストの小さいものの和でも出力しておくことにしよう．
入力の最初の行は2つの整数 N, M を含む．これは，グラフの頂点数と辺数を表す． 続く M 行は，辺の情報を表す．これらの行のうちのi行目には3つの整数 ui, vi, di が書かれており， 頂点 ui から出て頂点 vi へ行くコスト di の辺であることを表す．
各頂点から出て行く辺のうち最もコストの小さいものの和を出力せよ．
入力例1:
3 6 1 2 1 1 3 2 2 1 2 2 3 1 3 2 2 3 1 1
入力例 1 に対する出力の例:
3