#nullable enable #region var (_input, _iter) = (Array.Empty(), 0); T I() where T : IParsable { while (_iter >= _input.Length) (_input, _iter) = (Console.ReadLine()!.Trim().Split(' '), 0); return T.Parse(_input[_iter++], null); } #endregion static T[] Range(int n, Func F) => Enumerable.Range(0, n).Select(_ => F()).ToArray(); var n = I(); var m = I(); var q = I(); var sz = Range(n, I); var max = sz.Max() * 2; var oez = Range(m, () => (I() - 1, I() - 1, I())); var zz = new UnionFind(n); foreach (var (u, v, w) in oez) if (w == 0) zz.Union(u, v); var ez = new List<(int, int, long)>(); var fz = new Dictionary(); { var k = 1L; for (var i = 0; i < m; i++) { k = Math.Min(k * 2, max + 1); var (u, v, w) = oez[i]; u = zz.Find(u); v = zz.Find(v); if (u == v || w > max / k) continue; w *= k; ez.Add((u, v, w)); if (!fz.ContainsKey(u)) fz[u] = fz.Count; if (!fz.ContainsKey(v)) fz[v] = fz.Count; } } m = fz.Count; var fd = Range(m, () => new long[m]); for (var i = 0; i < m; i++) for (var j = 0; j < m; j++) fd[i][j] = max; for (var i = 0; i < m; i++) fd[i][i] = 0; foreach (var (u, v, w) in ez) fd[fz[u]][fz[v]] = fd[fz[v]][fz[u]] = Math.Min(fd[fz[u]][fz[v]], w); foreach (var (k, ki) in fz) { foreach (var (u, ui) in fz) foreach (var (v, vi) in fz) { var nd = fd[ui][ki] + fd[ki][vi]; fd[ui][vi] = Math.Min(fd[ui][vi], nd); } } long Solve(int ab, int ad) { ab = zz.Find(ab); ad = zz.Find(ad); if (ab == ad) return 0; var res = sz[ab] + sz[ad]; if (fz.ContainsKey(ab) && fz.ContainsKey(ad)) res = Math.Min(res, fd[fz[ab]][fz[ad]]); if (fz.TryGetValue(ab, out var i)) foreach (var (v, vi) in fz) res = Math.Min(res, fd[i][vi] + sz[v] + sz[ad]); if (fz.TryGetValue(ad, out var j)) foreach (var (v, vi) in fz) res = Math.Min(res, fd[j][vi] + sz[v] + sz[ab]); return res; } var ans = Range(q, () => Solve(I() - 1, I() - 1)); Console.WriteLine(string.Join(Environment.NewLine, ans)); class UnionFind { int[] Verticals { get; set; } public UnionFind(int verticals) { Verticals = new int[verticals]; Verticals.AsSpan().Fill(-1); } public int Union(int x, int y) { (x, y) = (Find(x), Find(y)); if (x == y) return x; var (sx, sy) = (Size(x), Size(y)); if (sx < sy) (x, y, sy) = (y, x, sx); Verticals[x] -= sy; return Verticals[y] = x; } public int Find(int x) { var p = Verticals[x]; if (p < 0) return x; return Verticals[x] = Find(p); } public int Size(int x) => -Verticals[Find(x)]; }