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