埃歐埃西國有 $N$ 座城市，編號為 $1,2,\dots,N$，在這些城市之間有 $M$ 條跨城市道路，其中第 $i$ 條道路雙向連接城市 $u_i,v_i$，並且長度為 $w_i$。特別的是，因為埃歐埃西國的國王不喜歡有一樣長度的跨城市道路，不然路長得太像他會迷路，因此這 $M$ 條跨城市道路的長度都是不同的。

若葉特石是一個天才演員，他希望能以最快的速度讓他的名聲響徹整個埃歐埃西國。一開始，他會選擇一座城市 $s$ 作為他的活動根據地，作為一個天才演員，他不需要花費什麼力氣和錢就可以成為整個城市 $s$ 中最受歡迎的演員，不過由於埃歐埃西國的城市之間資訊不太流通，他必須要做點什麼才能讓城市 $s$ 以外的其他城市的居民認識他。

對於一座城市 $v$，若葉特石可以舉辦一場城市 $s,v$ 之間的文化交流會，城市 $v$ 的居民就會在這場文化交流會中看見若葉特石的表演，並且視若葉特石為城市 $v$ 最受歡迎的演員。如果從 $s$ 到 $v$ 之間由跨城市道路構成的最短路徑長度是 $d(s,v)$，那麼這場文化交流會就要花費 $d(s,v)$ 元。

一旦一座城市的居民視若葉特石為最受歡迎的演員之後，他們就會永遠這麼認為，但若葉特石只能透過文化交流會的方式來成為新的城市的最受歡迎演員，他可以按照相同的方式，先挑一座他是最受歡迎演員的城市 $u$（不一定要是 $s$！）、一座他不是最受歡迎演員的城市 $v$，舉辦 $u,v$ 之間的文化交流會，然後他就會成為城市 $v$ 的最受歡迎演員，同樣地這會花費 $d(u,v)$ 元，其中 $d(u,v)$ 是兩個城市之間由跨城市道路構成的最短路徑長。

雖然若葉特石有很多贊助商，但錢還是能省則省，才能拿去做更多好玩的事情，因此他在選定根據地城市 $s$ 之後，會不斷找到一個他是最受歡迎演員的城市 $u$，以及一個他不是最受歡迎演員的城市 $v$，所有這種 $u,v$ 之中 $d(u,v)$ 最小的那一對（可以證明，$d(u,v)$ 最小的 $u,v$ 只有唯一一對），然後舉辦 $u,v$ 之間的文化交流會，直到他是全部 $N$ 個城市的最受歡迎演員為止。

為了研究哪個城市最適合作為活動根據地以及他聲名遠播的速度，若葉特石有 $Q$ 個問題，第 $i$ 個問題以兩個城市的編號 $s_i,t_i$ 表示，代表他想知道如果他一開始選擇以 $s_i$ 作為活動根據地，按照上述的策略，要舉辦幾次文化交流會，若葉特石才會成為城市 $t_i$ 的最受歡迎演員。