N 个景区，任意两个景区之间有一条或多条双向的路来连接，现在 Mr.Zeng 想找一条旅游路线，这个路线从A点出发并且最后回到 A 点，假设经过的路线为 V1，V2，....VK，V1，那么必须满足 K>2，就是说至除了出发点以外至少要经过 2 个其他不同的景区，而且不能重复经过同一个景区。不存在这样的景区X：从 X 出发不到达其他景区马上回到 X。现在 Mr.Zeng 需要你帮他找一条这样的路线，并且长度越小越好。

第一行包含两个正整数：景区个数 N (N<=100)，另一个是道路的数目 M (M<10000)。
接下来 M 行每行描述一条路，每一行有三个正整数 A,B,C，其中 A 和 B 分别表示这条路连接的两个景区的编号，C 表示这条路的长度（不超过 500 的正整数）。

如果这条观光路线是不存在的话就显示“No solution.”(有句号)；
如果这条观光路线存在就输出经过的最小长度。

输入　 [复制]

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

输出

61

【样例说明】
经过路线 1 3 5 2 1，长度：10+20+15+16=61

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cmath>

#include<ctime>

#include<cctype>

#include<cstring>

#include<string>

#include<algorithm>

using namespace std;

const int inf=1e+;

const int N=;

const int M=;

int n,m,dis[N][N],dp[N][N];

int R()

{

  char c;

  int f=;

  for(c=getchar();c<''||c>'';c=getchar());

  for(;c>=''&&c<='';c=getchar())

    f=(f<<)+(f<<)+c-'';

  return f;

}

int floyd()

{

  int minn=inf;

  for(int k=;k<=n;k++)

  {

    for(int i=;i<k;i++)

      for(int j=i+;j<k;j++)

        minn=min(dp[i][j]+dis[i][k]+dis[k][j],minn);

    for(int i=;i<=n;i++)

      for(int j=;j<=n;j++)

        dp[i][j]=min(dp[i][k]+dp[k][j],dp[i][j]);

  }

  return minn;

}

int main()

{

  //freopen("a.in","r",stdin);

  n=R();

  m=R();

  for(int i=;i<=n;i++)

    for(int j=;j<=n;j++)

      dis[i][j]=dp[i][j]=inf;

  int a,b,c;

  for(int i=;i<=m;i++)

  {

    a=R();

    b=R();

    c=R();

    dis[a][b]=dis[b][a]=dp[a][b]=dp[b][a]=min(dis[a][b],c);

  }

  int ans;

  ans=floyd();

  if(ans==inf)

    cout<<"No solution."<<endl;

  else

    cout<<ans<<endl;

  return ;

}