題目描述

有N個(gè)空間站通過M個(gè)通道連接起來，第i條太空通道從太空站ai開始，到太空站bi結(jié)束，需要ti個(gè)小時(shí)完成通行。對(duì)于需要在不同空間站工作的人來說，希望盡可能少的通過不同通道，以減少不可預(yù)知的時(shí)間開銷。小明就限制自己每次出行最多通過k條不同通道。現(xiàn)在請(qǐng)你幫小明計(jì)算，從太空站Sj到Ej之間旅行時(shí)，最多經(jīng)過k條通道，最短的通行時(shí)間是多少？

輸入說明

第一行包括2個(gè)數(shù)字，分別表示N和M (2 ≤N≤ 70, 1 ≤M≤ 10^6);

接下來M行，每行包括3個(gè)整數(shù)，分別表示ai, bi和ti (1 ≤ ai, bi ≤ N, 1 ≤ ti ≤ 10^6);

之后一行包括2個(gè)正整數(shù)，分別表示k和q (1 ≤ k ≤ 10^9, 1 ≤ q ≤ N^2)，即最多通過k條不同的通道和查詢次數(shù);

接下來q行，每行2個(gè)整數(shù)(1 ≤ Sj , Ej ≤ N)，表示每次查詢的出發(fā)空間站和到達(dá)空間站。

輸出說明

輸出每次通行計(jì)劃對(duì)應(yīng)的最短時(shí)間，占一行。如果沒有滿足條件的通行線路，請(qǐng)輸出-1。