import std.algorithm, std.array, std.container, std.range; import std.string, std.conv, std.math; import std.stdio, std.typecons; alias Tuple!(int, "v", int, "c") side; void main() { auto n = readln.chomp.to!int; auto sti = iota(n).map!(i => readln.chomp.to!int).array; auto graph = new side[][n]; auto m = readln.chomp.to!int; foreach (i; 0..m) { auto rd = readln.split.map!(to!int); graph[rd[0]] ~= side(rd[1], rd[2]); graph[rd[1]] ~= side(rd[0], rd[2]); } auto min = int.max; foreach (s1; 1..(n - 1)) { foreach (s2; 1..(n - 1)) { if (s1 == s2) continue; auto r = dijkstra(n, 0, s1, graph) + dijkstra(n, s1, s2, graph) + dijkstra(n, s2, n - 1, graph) + sti[s1] + sti[s2]; if (r < min) min = r; } } writeln(min); } int dijkstra(int n, int s, int e, side[][] graph) { auto memo = new int[n]; auto visited = new bool[n]; visited[s] = true; auto pq = Array!side().heapify!("a.c > b.c"); foreach (si; graph[s]) pq.insert(si); while (!pq.empty) { auto si = pq.front; pq.removeFront; if (visited[si.v]) continue; if (si.v == e) return si.c; memo[si.v] = si.c; visited[si.v] = true; foreach (c; graph[si.v]) { if (!visited[c.v]) { pq.insert(side(c.v, si.c + c.c)); } } } return memo[e]; }