TopCoder

aacpschool

User's AC Ratio

100.0% (2/2)

100.0% (2/2)

有一個推銷員要推銷他的百科全書，因此要走訪 $N$ 座城市後回家。這 $N$ 座城市之間有 $M$ 條雙向鐵路相連，其中連接 $u_i, v_i$ 的鐵路路程為 $w_i$。推銷員需要選擇任意一座城市作為出發地，並且不重複的經過所有城市恰一次，最後回到出發點。請回答推銷員所需經過的最短旅程長度。

輸入第一行是兩個以空白分隔的整數 $N, M$，分別代表城市和鐵路數量。

接下來有 $M$ 行，每行有三個以空白分隔的整數 $u,v,w$，分別代表鐵路連接的兩個城市和距離。

輸入保證 $3\le N\le 10$，$3\le M \le \frac{N(N-1)}2$，$1\le u,v\le N$，$1\le w\le 10^ 6$。
且沒有兩條鐵路有相同的起終點，也沒有一條連接兩個相同城市的鐵路。

輸出一行一個整數，表示最短旅行距離。如果不存在一條路徑可以完成，請輸出 $-1$。

3 3
1 2 5
2 3 2
3 1 3

4 4
1 2 5
1 3 6
1 4 7
3 4 2

-1

No.	Testdata Range	Constraints	Score
1	0~1	範例測資	0
2	0~12	無額外限制	100

No.	Time Limit (ms)	Memory Limit (VSS, KiB)	Output Limit (KiB)	Subtasks
0	1000	524288	65536	1 2
1	1000	524288	65536	1 2
2	1000	524288	65536	2
3	1000	524288	65536	2
4	1000	524288	65536	2
5	1000	524288	65536	2
6	1000	524288	65536	2
7	1000	524288	65536	2
8	1000	524288	65536	2
9	1000	524288	65536	2
10	1000	524288	65536	2
11	1000	524288	65536	2
12	1000	524288	65536	2