import static java.lang.Math.*;
import static java.util.Arrays.*;
import java.util.*;

public class Main {
	Scanner sc = new Scanner(System.in);
	
	int INF = 1 << 29;
	
	// dp[S][t] : sからスタートし，Sを巡ってtに到達する最小コスト
	int[][] tsp(int[][] g, int s) {
		int n = g.length;
		int[][] dp = new int[1 << n][n];
		for (int i = 0; i < 1 << n; i++) fill(dp[i], INF);
		dp[1 << s][s] = 0;
		for (int S = 0; S < 1 << n; S++) {
			for (int t = 0; t < n; t++) if (dp[S][t] < INF) {
				for (int v = 0; v < n; v++) if ((S >> v & 1) == 0) {
					if (dp[S | 1 << v][v] > dp[S][t] + g[t][v]) {
						dp[S | 1 << v][v] = dp[S][t] + g[t][v];
					}
				}
			}
		}
		return dp;
	}
	
	// res[s][t][S] : sから入り，内部の都市全てと空港Sを巡ってtに到達する最小コスト
	// F=4の場合は16の位置に二分割のパターンが入る
	int[][][] calcLand(int[][] g, int F) {
		int n = g.length;
		int[][][] dp = new int[F][1 << n][n];
		for (int s = 0; s < F; s++) {
			dp[s] = tsp(g, s);
		}
		int[][][] res = new int[F][F][(1 << F) + (F == 4 ? 1 : 0)];
		int inside = ((1 << (n - F)) - 1) << F, all = (1 << n) - 1;
		for (int s = 0; s < F; s++) {
			for (int t = 0; t < F; t++) {
				for (int S = 0; S < 1 << F; S++) {
					res[s][t][S] = dp[s][S | inside][t];
				}
			}
		}
		if (F == 4) {
			for (int s = 0; s < F; s++) {
				for (int t = 0; t < F; t++) if (s != t) {
					int s2 = 0, t2 = F - 1;
					while (s2 == s || s2 == t) s2++;
					while (t2 == s || t2 == t) t2--;
					int tmp = INF;
					for (int S = 0; S < 1 << n; S++) {
						if (tmp > dp[s][S][t] + dp[s2][all ^ S][t2]) {
							tmp = dp[s][S][t] + dp[s2][all ^ S][t2];
						}
					}
					res[s][t][16] = tmp;
				}
			}
		}
		return res;
	}
	
	int[] encode = new int[32], decode = new int[22];
	{
		for (int i = 0; i < 15; i++) encode[i] = decode[i] = i;
		int id = 0;
		for (int i = 0; i < 4; i++) {
			for (int j = 0; j < i; j++) {
				encode[16 | 1 << i | 1 << j] = 15 + id;
				decode[15 + id] = 16 | 1 << i | 1 << j;
				id++;
			}
		}
		encode[15] = 21;
		decode[21] = 15;
	}
	
	// used[i]=S: 国iに関する訪れた都市の情報
	// S<16の場合，訪れた空港がSで，|S|<=1なら内部は空，|S|>=2は内部は全部訪れている
	// S>=16の場合，二つの空港を訪れており，残りの空港間はコスト0で移動可能 (前もってその分のコストが足されている)
	int[] decode(int id, int[] F) {
		int[] res = new int[F.length];
		for (int i = 0; i < F.length; i++) {
			if (F[i] == 4) {
				res[i] = decode[id % 22];
				id /= 22;
			} else {
				res[i] = id % (1 << F[i]);
				id >>= F[i];
			}
		}
		return res;
	}
	
	void run() {
		while (sc.hasNext()) {
			int N = sc.nextInt(), K = sc.nextInt();
			if ((N|K) == 0) return;
			int[] M = new int[N], F = new int[N];
			for (int i = 0; i < N; i++) M[i] = sc.nextInt();
			for (int i = 0; i < N; i++) F[i] = sc.nextInt();
			int[] id = new int[N + 1];
			for (int i = 0; i < N; i++) id[i + 1] = id[i] + F[i];
			int n = id[N]; // 空港の総数
			int[] country = new int[n]; // 各空港の属する国
			for (int i = 0; i < N; i++) for (int j = 0; j < F[i]; j++) country[id[i] + j] = i;
			int[][][] land = new int[N][][]; // 陸路のグラフ
			int[][] air = new int[n][n]; // 空路のグラフ
			for (int i = 0; i < N; i++) {
				land[i] = new int[M[i]][M[i]];
				for (int j = 0; j < M[i]; j++) fill(land[i][j], INF);
			}
			for (int i = 0; i < n; i++) fill(air[i], INF);
			for (int i = 0; i < K; i++) {
				int u1 = sc.nextInt() - 1, u2 = sc.nextInt() - 1;
				int v1 = sc.nextInt() - 1, v2 = sc.nextInt() - 1;
				if (u1 == v1) land[u1][u2][v2] = land[u1][v2][u2] = sc.nextInt();
				else air[id[u1] + u2][id[v1] + v2] = air[id[v1] + v2][id[u1] + u2] = sc.nextInt();
			}
			if (N == 1) {
				// 国が一つのケースは普通にTSPで解く
				if (M[0] == 1) {
					System.out.println(0);
					continue;
				}
				int[][] dp = tsp(land[0], 0);
				int res = INF;
				for (int i = 0; i < M[0]; i++) res = min(res, dp[(1 << M[0]) - 1][i] + land[0][i][0]);
				System.out.println(res < INF ? res : -1);
				continue;
			}
			int[][][][] dpLand = new int[N][][][];
			int[] ms = new int[N + 1];
			ms[0] = 1;
			for (int i = 0; i < N; i++) {
				dpLand[i] = calcLand(land[i], F[i]);
				ms[i + 1] = ms[i] * (F[i] == 4 ? 22 : (1 << F[i]));
			}
			int m = ms[N];
			int res = INF;
			int p = 0;
			for (int i = 0; i < N; i++) if (F[p] > F[i]) p = i;
			for (int init = id[p]; init == id[p] || init + 1 < id[p + 1]; init++) {
				int[][] dpAir = new int[m][n]; // dpAir[i][j]: 訪れた都市の情報がiで現在j番の空港から海外へ向かっている
				for (int i = 0; i < m; i++) fill(dpAir[i], INF);
				dpAir[0][init] = 0;
				for (int i = 0; i < m; i++) {
					int[] used = decode(i, F);
					for (int j = 0; j < n; j++) if (dpAir[i][j] < INF) {
						for (int c = 0; c < N; c++) {
							for (int s = 0; s < F[c]; s++) if ((used[c] >> s & 1) == 0 && air[j][id[c] + s] < INF) {
								int cost = dpAir[i][j] + air[j][id[c] + s];
								int count = Integer.bitCount(used[c]);
								if (used[c] < 16) {
									if (F[c] == M[c] || count <= 1) {
										// 内部の都市全てと空港Sを巡ってtから出国
										for (int t = 0; t < F[c]; t++) if ((used[c] >> t & 1) == 0) {
											int sup = ((1 << F[c]) - 1) & ~(used[c] | 1 << s | 1 << t);
											int sub = sup;
											do {
												int S = used[c] | sub | 1 << s | 1 << t;
												int i2 = i + (encode[S] - encode[used[c]]) * ms[c];
												int cost2 = cost + dpLand[c][s][t][sub | 1 << s | 1 << t];
												if (dpAir[i2][id[c] + t] > cost2) {
													dpAir[i2][id[c] + t] = cost2;
												}
												sub = (sub - 1) & sup;
											} while (sub != sup);
										}
										if (F[c] == M[c]) continue;
									}
									if (count >= 2 || F[c] >= 3 && count == 0) {
										// すぐに海外へ
										int i2 = i + (encode[used[c] | 1 << s] - encode[used[c]]) * ms[c];
										if (dpAir[i2][id[c] + s] > cost) {
											dpAir[i2][id[c] + s] = cost;
										}
									} else if (F[c] == 4 && count == 1) {
										// すぐに海外へ，残りの街の巡り方が確定
										int i2 = i + (encode[used[c] | 1 << s | 16] - encode[used[c]]) * ms[c];
										int s2 = 0, t2 = 3;
										while (s2 == s || (used[c] >> s2 & 1) != 0) s2++;
										while (t2 == s || (used[c] >> t2 & 1) != 0) t2--;
										int cost2 = cost + dpLand[c][s2][t2][1 << s2 | 1 << t2];
										if (dpAir[i2][id[c] + s] > cost2) {
											dpAir[i2][id[c] + s] = cost2;
										}
									}
									if (F[c] == 4 && count == 0) {
										// 二分割
										for (int t = 0; t < 4; t++) if (s != t) {
											int i2 = i + (encode[1 << s | 1 << t | 16] - encode[used[c]]) * ms[c];
											int cost2 = cost + dpLand[c][s][t][16];
											if (dpAir[i2][id[c] + t] > cost2) {
												dpAir[i2][id[c] + t] = cost2;
											}
										}
									}
								} else {
									// 他方の空港へコスト0で移動
									int t = 0;
									while (t == s || (used[c] >> t & 1) != 0) t++;
									int i2 = i + (encode[15] - encode[used[c]]) * ms[c];
									if (dpAir[i2][id[c] + t] > cost) {
										dpAir[i2][id[c] + t] = cost;
									}
								}
							}
						}
					}
				}
				int[] used = new int[N];
				for (int i = 0; i < N; i++) used[i] = (1 << F[i]) - 1;
				res = min(res, dpAir[m - 1][init]);
			}
			System.out.println(res == INF ? -1 : res);
		}
	}
	
	void debug(Object...os) {
		System.err.println(deepToString(os));
	}
	
	public static void main(String[] args) {
		new Main().run();
	}
}