Problem : 15 - 搬家

Problem Statistics

Solved Member: 36　　Submission: 186　　User Tried: 38

Statement:

如此這般，你搬到了你嚮往以久的北海道居住。

◯北海道一隅

到了一個新地方的念頭當然就是先把附近有名的景點弄熟！你列出了N(1 <= N <=100)個景點，分別由1編號到N，以及M(1 <= M <= 10000)條道路，每條道路連接著兩個景點。

你決定選擇N個景點當中的其中一個當作起點，隨意繞過任幾個不重複的景點再回到原地，並且你希望你走過不同的景點至少有3個。由於你剛剛搭飛機來北海道你非常非常的累，所以你希望讓旅途盡量短一點這樣你可以快點回家睡覺。

Input:Output:

第1行有兩個正整數N,M，代表地標數以及道路數。
接下來的M行各有三個整數i,j,k，代表i景點到j景點存在一條距離k的雙向道路。

只有一行，輸出最短的距離。如果不存在這樣的路徑，請你輸出"No solution."(不含括號)。

Sample Input:Sample Output:

5 7
1 4 1
1 3 300
3 1 10
1 2 16
2 3 100
2 5 15
5 3 20

Source:

CEOI 1999

Problem Setter

Nekosyndrome

Testdata:

Test	Time	Memory	Score
0	300ms	16384kb
1	300ms	16384kb	10
2	300ms	16384kb	10
3	300ms	16384kb	10
4	300ms	16384kb	10
5	300ms	16384kb	10
6	300ms	16384kb	10
7	300ms	16384kb	10
8	300ms	16384kb	10
9	300ms	16384kb	10
10	300ms	16384kb	10