// Arup Guha
// 4/29/2019
// Solution to 2012 NCPC Problem F: Food Review

import java.util.*;

public class foodreview {

	final public static int NOEDGE = 1000000000;
	public static int n;
	public static HashMap<Long, Integer> memo;
	public static boolean[] need;
	
	public static void main(String[] args) {

		Scanner stdin = new Scanner(System.in);
		n = stdin.nextInt();
		int edges = stdin.nextInt();

		// Set up adjacency matrix.
		int[][] adj = new int[n][n];
		for (int i=0; i<n; i++) {
			Arrays.fill(adj[i], NOEDGE);
			adj[i][i] = 0;
		}
		
		// Will store each place we must visit.
		need = new boolean[n];
		need[0] = true;		
		int[] degree = new int[n];
		int cost = 0;
		int[] dj = new int[n];
		for (int i=0; i<n; i++) dj[i] = i;
		
		// Read in flights we must take.
		for (int i=0; i<edges; i++) {
			int v1 = stdin.nextInt()-1;
			int v2 = stdin.nextInt()-1;
			int w = stdin.nextInt();
			cost += w;
			adj[v1][v2] = Math.min(adj[v1][v2], w);
			adj[v2][v1] = Math.min(adj[v1][v2], adj[v2][v1]);
			degree[v1]++;
			degree[v2]++;
			need[v1] = true;
			need[v2] = true;
			union(dj, v1, v2);
		}
		
		// Pretend that if we don't need you, that you are in the tree with 0.
		for (int i=0; i<n; i++)
			if (!need[i])
				dj[i] = 0;
		
		// Process extra flights, only storing best.
		int extra = stdin.nextInt();
		for (int i=0; i<extra; i++) {
			int v1 = stdin.nextInt()-1;
			int v2 = stdin.nextInt()-1;
			int w = stdin.nextInt();
			adj[v1][v2] = Math.min(adj[v1][v2], w);
			adj[v2][v1] = Math.min(adj[v1][v2], adj[v2][v1]);
		}

		// Floyd's since we'll patch up extra places we have to visit with shortest
		// paths, not shortest edges.
		for (int k=0; k<n; k++)
			for (int i=0; i<n; i++)
				for (int j=0; j<n; j++)
					adj[i][j] = Math.min(adj[i][j], adj[i][k]+adj[k][j]);

		// Calculate how many extra times we must visit each vertex.
		int mask=0;
		for (int i=0; i<n; i++)
			mask += ((degree[i]%2) << i);
		
		memo = new HashMap<Long,Integer>();

		// Makes all degrees even.
		cost += solve(mask, dj, adj);
		System.out.println(cost);
	}
	
	// Effectively a disjoint set union where we always store your root node directly.
	public static void union(int[] dj, int v1, int v2) {
		int t1 = dj[v1], t2 = dj[v2];
		int par = Math.min(t1, t2);
		for (int i=0; i<n; i++)
			if (dj[i] == t1 || dj[i] == t2)
				dj[i] = par;
	}

	// Returns the solution given that mask stores the parity of the degree vertices and dj stores
	// the connectivity data (as a disjoint set, sort of).
	public static int solve(int mask, int[] dj, int[][] adj) {
		
		// For hashmap storage purposes.
		long code = getCode(mask, dj);
		
		// This is the unique mask where we are done.
		if (code == 0) return 0;

		// We did this before.
		if (memo.containsKey(code)) return memo.get(code);
		
		int best = NOEDGE;

		// I am just going to try everything.
		for (int start=0; start<n; start++) {
			for (int end=start+1; end<n; end++) {
			
				if (adj[start][end] == NOEDGE) continue;
				if (!need[end]||!need[start]) continue;
			
				// To make Chinese Postman Tours, we only want to grab odd vertices OR merge trees.
				if (  ( ((mask & (1 << end)) != 0) && ((mask & (1 << start)) != 0) ) || (dj[start] != dj[end]) ) {
				
					// Try this and just use a new copy of the disjoint set.
					int[] newdj = Arrays.copyOf(dj, n);
					if (dj[start] != dj[end]) union(newdj, start, end);
					int cur = adj[start][end] + solve(mask ^ (1<<start) ^ (1<<end), newdj, adj);
					best = Math.min(best, cur);	
				}
			}
		}

		// Store and return.
		memo.put(code, best);
		return best;
	}
	
	// Here is the code we are using.
	public static String bits(long code) {
		String res = "";
		while (code != 0) {
			res = (code&1) + res;
			code >>= 1;
		}
		return res;
	}
	
	// Condensed storage so I can use my hashmap with longs.
	public static long getCode(int mask, int[] dj) {
		long res = mask;
		for (int i=0; i<n; i++) {
			int bits = 3;
			if (i > 7) bits = 4;
			res = (res << bits) + dj[i];
		}
		return res;
	}
}

class edge implements Comparable<edge> {
	
	public int u;
	public int v;
	public int w;
	
	public edge(int a, int b, int myw) {
		u = a;
		v = b;
		w = myw;
	}
	
	public int compareTo(edge other) {
		return this.w - other.w;
	}
}