題目描述

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

輸入說明

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

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

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

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

輸出說明

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