时间限制：1秒　　内存限制：256M

---

【问题描述】

　　旅行社决定为其客户提供CQ市的观光旅游。为节约成本，旅行社需要找到一条始于同一地点并结束于同一地点的最短路线。这个任务需要你来编程完成。

　　在该市有 \(n\) 个编号为 \(1\) 到 \(n\) 的景点，有 \(m\) 条双向道路连接这些景点，两个景点可以通过多条道路连接，但没有道路连接同一个景点。

【输入格式】

　　第一行包含两个正整数：\(n\) 和 \(m\)，它们的意义如题目描述。
　　接下来的 \(m\) 行每行描述一条道路：\(u,v,d\)，表示该道路连接 \(u\) 和 \(v\) 两个景点，其长度为 \(d\)。

【输出格式】

　　输出符合条件的最短路线长度。若无解，输出 “No solution.”。

【输入输出样例1】

　Input

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

　Output

61

【样例1解释】

样例解释：一种可行的方案：1−3−5−2−1。

【输入输出样例2】

　Input

4 3
1 2 10
1 3 20
1 4 30

　Output

No solution.

【数据限制】

　　对于 \(20\%\) 的数据，\(n,m≤10\)；
　　对于 \(60\%\) 的数据，\(m≤100\)；
　　对于 \(100\%\) 的数据，\(1≤n≤100，1≤m≤5000，1≤d≤100000\)。
　　另外附加了三组数据，\(1≤n≤1000，1≤m≤300000，1≤d≤100000\)。

【来源】

　Mr.he