#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 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 = I() - 1; var v = I() - 1; var w = I(); if (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) { 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));