#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 fd = Range(n, () => new Dictionary()); var fz = new HashSet(); { 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; fd[u][v] = fd[v][u] = Math.Min(w, fd[u].GetValueOrDefault(v, max)); fz.Add(u); fz.Add(v); } } foreach (var v in fz) fd[v][v] = 0; foreach (var u in fz) foreach (var v in fz) { foreach (var k in fz) { var cd = fd[u].GetValueOrDefault(v, max); var nd = fd[u].GetValueOrDefault(k, max) + fd[k].GetValueOrDefault(v, max); fd[u][v] = Math.Min(cd, nd); } } long Solve(int ab, int ad) { var res = sz[ab] + sz[ad]; foreach (var u in fz) foreach (var v in fz) { var d = fd[u][v]; d += Math.Min(fd[u].GetValueOrDefault(ab, max), sz[ab] + sz[u]); d += Math.Min(fd[v].GetValueOrDefault(ad, max), sz[v] + sz[ad]); res = Math.Min(res, d); } return res; } var ans = Range(q, () => Solve(I() - 1, I() - 1)); Console.WriteLine(string.Join(Environment.NewLine, ans));