cf21D Traveling Graph

You are given undirected weighted graph. Find the length of the shortest cycle which starts from the vertex 1 and passes throught all the edges at least once. Graph may contain multiply edges between a pair of vertices and loops (edges from the vertex to itself).

Input

The first line of the input contains two integers n and m (1 ≤ n ≤ 15, 0 ≤ m ≤ 2000), n is the amount of vertices, and m is the amount of edges. Following m lines contain edges as a triples x, y, w (1 ≤ x, y ≤ n, 1 ≤ w ≤ 10000), x, y are edge endpoints, and w is the edge length.

Output

Output minimal cycle length or -1 if it doesn't exists.

Example

Input

Output

Input

3 2
1 2 3
2 3 4

Output

题意是给一个无向图，要求从1出发回到1，但是必须经过图中每一条边，只上一次

这从不从1出发有什么用呢？这就是个欧拉回路。

然后判一下每个点的度数是不是奇数，如果是奇数就需要再找个奇数度数的点匹配。

最后，匹配直接搜索就行。

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<cstring>
 4 #include<cstdlib>
 5 #include<algorithm>
 6 #include<cmath>
 7 #include<queue>
 8 #include<deque>
 9 #include<set>
10 #include<map>
11 #include<ctime>
12 #define LL long long
13 #define inf 0x7ffffff
14 #define pa pair<int,int>
15 #define mkp(a,b) make_pair(a,b)
16 #define pi 3.1415926535897932384626433832795028841971
17 using namespace std;
18 inline LL read()
19 {
20     LL x=0,f=1;char ch=getchar();
21     while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
22     while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
23     return x*f;
24 }
25 int n,m;
26 int v[110];
27 int fa[110];
28 int p[110],cnt;
29 bool mrk[110];
30 int dis[110][110];
31 LL ans,ans2;
32 struct edg{int x,y,z;}e[10010];
33 inline int getfa(int x){return fa[x]==x?x:fa[x]=getfa(fa[x]);}
34 inline void dfs(int now,LL tot)
35 {
36     if (now==cnt/2+1){ans2=min(ans2,tot);return;}
37     int x,y;
38     for (x=1;x<=cnt;x++)if (!mrk[x])break;
39     mrk[x]=1;
40     for (y=x+1;y<=cnt;y++)if (!mrk[y]&&dis[p[x]][p[y]]<=1000000)
41     {
42         mrk[y]=1;
43         dfs(now+1,tot+dis[p[x]][p[y]]);
44         mrk[y]=0;
45     }
46     mrk[x]=0;
47 }
48 int main()
49 {
50     n=read();m=read();
51     for (int i=1;i<=n;i++)fa[i]=i;
52     for (int i=1;i<n;i++)
53     for (int j=i+1;j<=n;j++)
54         dis[i][j]=dis[j][i]=1<<28;
55     for (int i=1;i<=m;i++)
56     {
57         e[i].x=read();
58         e[i].y=read();
59         e[i].z=read();v[e[i].x]++;v[e[i].y]++;
60         if (e[i].z<dis[e[i].x][e[i].y])dis[e[i].x][e[i].y]=dis[e[i].y][e[i].x]=e[i].z;
61         ans+=e[i].z;
62         int xx=getfa(e[i].x),yy=getfa(e[i].y);
63         if (xx>yy)swap(xx,yy);
64         fa[xx]=yy;
65     }
66     for (int i=1;i<=m;i++)
67     {
68         if (getfa(e[i].x)==getfa(1)&&getfa(e[i].y)==getfa(1))continue;
69         puts("-1");
70         return 0;
71     }
72     for (int k=1;k<=n;k++)
73         for (int i=1;i<=n;i++)
74             for (int j=1;j<=n;j++)
75                 if (dis[i][j]>dis[i][k]+dis[k][j])
76                     dis[i][j]=dis[i][k]+dis[k][j];
77     for (int i=1;i<=n;i++)if (v[i]&1)p[++cnt]=i;
78     if (cnt&1){puts("-1");return 0;}
79     ans2=1ll<<50;
80     dfs(1,ans);
81     printf("%lld
",ans2);
82 }

cf21D

Input

Output

Output minimal cycle length or -1 if it doesn't exists.

Example

Input

Output

Input

3 2
1 2 3
2 3 4

Output