#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 ez = Range(n, () => new List<(int, long)>()); { 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; ez[u].Add((v, w)); ez[v].Add((u, w)); } } var dz = new long[n]; dz.AsSpan().Fill(max); long Solve(int ab, int ad) { var mod = new HashSet(){ ab, ad }; dz[ab] = 0; dz[ad] = sz[ab] + sz[ad]; var queue = new PriorityQueue<(int, long), long>(); queue.Enqueue((ab, 0), 0); while (queue.Count > 0) { var (v, w) = queue.Dequeue(); if (dz[v] > w) continue; foreach (var (next, c) in ez[v]) { var nd = Math.Min(w + c, max); if (dz[next] <= nd) continue; dz[next] = nd; queue.Enqueue((next, nd), nd); mod.Add(next); dz[ad] = Math.Min(dz[ad], nd + sz[next] + sz[ad]); } } var res = dz[ad]; foreach (var v in mod) dz[v] = max; return res; } var ans = Range(q, () => Solve(I() - 1, I() - 1)); Console.WriteLine(string.Join(Environment.NewLine, ans));