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.

Examples

Input

3 3
1 2 1
2 3 1
3 1 1


Output

3


Input

3 2
1 2 3
2 3 4


Output

14
import java.io.*;
import java.util.*;
import static java.lang.Math.*;

public class Main
{
    int n, m;
    int[] d = new int[20];
    int[][] g = new int[20][20];
    int[][] dist = new int[20][20];
    int[] f = new int[66000];
    boolean[] used = new boolean[20];
    
    void dfs(int p)
    {
        used[p] = true;
        for(int i=1; i<=n; i++)
            if( !used[i] && g[p][i]!=Integer.MAX_VALUE )
                dfs(i);
    }
    boolean check()
    {
        dfs(1);
        for(int i=1; i<=n; i++)
            if( !used[i] && d[i]>0 )
                return false;
        return true;
    }
    int dp(int s)
    {
        if( f[s] != Integer.MAX_VALUE )
            return f[s];
        for(int i=1; i<=n; i++)
            if( (s&(1<<i)) != 0 )
                for(int j=i+1; j<=n; j++)
                    if( (s&(1<<j)) != 0 )
                        f[s] = min(f[s], dp(s^(1<<i)^(1<<j))+dist[i][j]);
        
        return f[s];
    }
    void run() throws IOException
    {
        int ans=0, u, v, w;
        
        n = cin.nextInt();
        m = cin.nextInt();
        for(int i=0; i<g.length; i++)
            Arrays.fill(g[i], Integer.MAX_VALUE);
        for(int i=1; i<=n; i++)
            g[i][i] = 1;
        for(int i=0; i<m; i++)
        {
            u = cin.nextInt();  v = cin.nextInt();  w = cin.nextInt();
            d[u]++;  d[v]++;
            ans += w;
            g[u][v] = min(g[u][v], w);
            g[v][u] = min(g[v][u], w);
        }
        
        if( !check() )
        {
            cout.println(-1);
            return;
        }
        
        dist = g.clone();
        for(int k=1; k<=n; k++)
            for(int i=1; i<=n; i++)
                for(int j=1; j<=n; j++)
                    if( dist[i][k]!=Integer.MAX_VALUE && dist[k][j]!=Integer.MAX_VALUE &&
                            dist[i][k]+dist[k][j]<dist[i][j] )
                        dist[i][j] = dist[i][k]+dist[k][j];
        
        int s = 0;
        for(int i=1; i<=n; i++)
            if( d[i]%2 == 1 )
                s = s|(1<<i);
        Arrays.fill(f, Integer.MAX_VALUE);
        f[0] = 0;
        cout.println(dp(s)+ans);
    }
    
    static FastScanner cin;
    static PrintWriter cout;
    public static void main(String[] args) throws IOException
    {
        Main instances = new Main();
        
        cin = new FastScanner(System.in);
        cout = new PrintWriter(System.out);
        instances.run();
        cout.close();
    }
}

class FastScanner
{
    BufferedReader reader;
    StringTokenizer tokenizer;
    
    public FastScanner(InputStream in)
    {
        reader = new BufferedReader(new InputStreamReader(in));
    }
    public String nextToken() throws IOException 
    {
        while (tokenizer == null || !tokenizer.hasMoreTokens())
            tokenizer = new StringTokenizer(reader.readLine());
        return tokenizer.nextToken();
    }
    public int nextInt() throws IOException
    {
        return Integer.parseInt(nextToken());
    }
    public long nextLong() throws IOException
    {
        return Long.parseLong(nextToken());
    }
    public double nextDouble() throws IOException
    {
        return Double.parseDouble(nextToken());
    }
}
