1 #include "iostream"
 2 #include "cstdio"
 3 #include "cstring"
 4 #include "algorithm"
 5 #include "vector"
 6 #include "queue"
 7 #include "cmath"
 8 #include "string"
 9 #include "cctype"
10 #include "map"
11 #include "iomanip"
12 using namespace std;
13 #define pb push_back
14 #define mp make_pair
15 #define fi first
16 #define se second
17 #define lc(x) (x << 1)
18 #define rc(x) (x << 1 | 1)
19 #define lowbit(x) (x & (-x))
20 #define ll long long
21 const int inf = 1 << 20;
22 int dp[11][65000];
23 int maz[15][15];
24 int p[15];
25 
26 void init() {
27     p[0] = 1;
28     for(int i = 1; i < 15; i++) p[i] = p[i-1] * 3;
29 }
30 
31 int n, m;
32 int main() {
33     int a, b, c;
34     init();
35     while(~scanf("%d%d", &n, &m)) {
36         for(int i =  0; i < n; i++)
37             for(int j = 0; j < n; j++)
38                 maz[i][j] = inf;
39         while(m--) {
40             cin >> a >> b >> c;
41             a--, b--;
42             if(c < maz[a][b]) maz[a][b] = maz[b][a] = c;
43         }
44 
45         int nn = p[n];
46         for(int i = 0; i < n; i++) {
47             for(int j = 0; j < nn; j++) dp[i][j] = inf;
48             dp[i][p[i]] = 0;
49         }
50         
51         for(int j = 0; j < nn; j++) {
52             for(int i = 0; i < n; i++) {
53                 int x = j / p[i] % 3;
54                 if(x > 0) {
55                     for(int k = 0; k < n; k++) {
56                         int y = j / p[k] % 3;
57                         if(maz[i][k] != inf && y <= 1)  {
58                             int nmask = j + p[k];
59                             dp[k][nmask] = min(dp[k][nmask], dp[i][j] + maz[i][k]);
60                         }
61                     }
62                 }
63             }
64         }
65         int ans = inf;
66         for(int i = 0; i < n; i++) {
67             for(int j = 0; j < nn; j++) {
68                 bool flag = true;
69                 for(int k = 0; k < n; k++)
70                     if((j / p[k] % 3) == 0) {
71                         flag = false;
72                         break;
73                     }
74                 if(flag) ans = min(ans, dp[i][j]);
75             }
76         }
77 
78         if(ans != inf) cout << ans << endl;
79         else cout << -1 << endl;
80     }
81     return 0;
82 }
83