2011 年のあの頃，まだプログラミングコンテストはとても平和であり， 我々はルールを精読せずに気軽にコンテストに参加していた． しかし，そこに G○○gle の陰謀は迫っていた． ある日，G○○gle によって秘密裏に買収されていた T○pC○der のコンテストは， 人知れずうちにルールが改変されており，命がけのプログラミングコンテストとなっていた． そして僕は，そこで，何も知らず， まっ先に kita_masa のプログラムのオーバーフローを突いたのだ…．
…そういえば，今こいつは，部屋に居る全ての人間を一瞬にして倒していた． どうなっているんだ？
…なるほど!! そういうことか． 彼は大学時代，指数時間のアルゴリズムを高速にすることに興味を持っていた． 例え指数時間であっても，指数の底が極めて小さければ， 現実的なインスタンスに対して十分に高速な可能性がある．
凄まじい，想像以上だ…．
グラフが与えられる． グラフはN 個の頂点を持ち，頂点には 1 から N の番号が付いている． また，グラフは M 個の辺を持ち，辺は有向 (一方通行) で， それぞれ距離が決まっている．
頂点 1 から出発し，頂点 2, 3, …, N をこの順番に訪れ，頂点 1 へ戻る経路を考える． ここで，「この順番に訪れる」というのは，経路に含まれる頂点の部分列に 2, 3, …, N が含まれるということである． つまり，スタート地点の頂点 1 から頂点 2 への移動は， 直接の移動であっても，他の頂点を経由した移動であってもよく， 次の頂点 2 から頂点 3への移動， さらにその次の頂点 3 から頂点 4への移動等に関しても同様である． 同じ頂点や同じ辺を 2 度通っても構わない．
グラフが与えられた時， 頂点 1 から出発し頂点 2, 3, …, N をこの順番に訪れ頂点 1 へ戻る経路のうち， 最短のものの長さを出力するプログラムを作成せよ． 経路の長さとは，経路に含まれる辺の距離の和である． 複数回含まれる辺に関しては，含まれる回数の分だけ距離を加えよ．
入力の最初の行は 2 つの整数 N, M を含む． これは，グラフの頂点数と辺数を表す．
続く M 行は，辺の情報を表す． これらの行のうちの i 行目は 3 つの整数 ai, bi, ci が書かれており， 辺 i は頂点 ai から頂点 bi を結び，その距離は ci であることを表す．
条件を満たす経路のうち最短のものの長さを出力せよ． ただし，条件を満たす経路が存在しない場合は，-1 を出力せよ．
入力例 1:
5 5 1 2 10 2 3 20 3 4 30 4 5 40 5 1 50
入力例 1 に対する出力の例:
150
入力例 2:
5 5 1 5 10 5 4 20 4 3 30 3 2 40 2 1 50
入力例 2 に対する出力の例:
600