0953 - 安い商品を求めて

時間制限 1 秒 / メモリ制限 64 MB / 得点 1 / Writer ei1719 / x 6 / 統計 /

TLE
1sec
MLE
64MB
得点
1

あらすじ

新しくグラフィックボードを購入したei1719。さっそくpcにつけてみたらBIOSの警告音がなってしまった！いろいろ調べてみると、そのエラーはグラフィックボードの差し込み具合が甘いとなるものらしい。もう一度外してつけてみたが、またエラー。もう一度つけてもまたエラー。いろいろ調べてみるとどうやらグラフィックボードは力を入れて刺さないといけないらしい。少し怖かったが力を込めて刺してみたら...


P C I　E x p r e s s　の　爪　が　折　れ　た
(実話)

とても落ち込んだが、壊れてしまったものは仕方がない。新規一転、新しいマザーボードを買ういい機会だと思って積極的に見ることにした。幸い、うちの近くにはドス〇ラやナ〇シマなどのPC専門店がある。せっかく買うのだから同じマザーボードでも安いマザーボードを買いたい。なので付近にある全部のpc専門店を回ることにした。しかし、全部の店を回るのは時間がかかるので最短経路で回りたい。マザーボードを壊し、落ち込んでるei1719のために自宅からすべての店を回り、自宅へ戻ってくるまでの最短経路を教えてあげよう！

問題

n個の店、およびm本の道がある。
自宅から開始し、すべての店に行き、自宅に戻るまでの最短経路の距離を求めよ。
ただし、一つの店は一回しか通ってはならない。
また、道はすべて一方通行であり、逆方向には移動できないことに注意せよ。

入力例

入力は複数の行からなる

n m
s1 e1 d1
s2 e2 d2
:
sn en dn

一行目に、店の数nと道の数mが与えられる。
二行目からm行にわたり店sから店eへの移動距離の情報が与えられる。
i番目は、店siから店eiにdiの距離があることを示す。

出力

自宅から、すべての店を行き、自宅に戻る最短経路の距離を出力せよ
そのような経路がない場合は、-1を出力せよ

制約

  • 0 < n < 15
  • 0 < m ≦ 210
  • 0 ≦ d ≦ 1000
  • 0 ≦ s,e ≦ n
  • si ≠ ei
  • すべての道において、s,eが全く同じになる道は存在しない。

s,eは0が自宅を表し、1~nがそれぞれの店を表す。

入出力例

入力例2

3 9
0 1 2
0 2 8
1 2 3
1 3 9
2 0 1
2 1 16
2 3 6
3 2 4
3 0 1

出力例1

12

解説

自宅(0)→1→2→3→自宅(0)の順で通れば、最短で通ることができる。

入力例2

4 8
0 1 5
1 0 3
0 2 10
1 2 3
2 3 5
0 3 1
0 4 2
3 4 9

出力例2

-1

入力例3

4 11
0 3 9
4 3 1
3 1 8
2 1 3
1 3 5
0 2 9
4 0 1
3 4 0
2 0 1
1 0 3
4 2 10

出力例3

18