哲哲最喜歡旅行了，但由於他荷包並沒有很胖，所以他只能在他所住的國家－ck國中旅行。ck國有$N$個城市(編號$1$到$N$)，並且有$N-1$條雙向連接兩個城市的道路，其中第$j$條道路的長度為$w_j$。並且保證任兩個城市之間都可以藉由走一些道路從其中一個城市到達另一個。

哲哲安排了$Q$次旅行，其中第$i$次(依照時間先後排序)旅行，他打算從城市$a_i$走最短路徑到城市$b_i$，由於他想知道每次旅行大概要花多少時間，所以他請你幫他找出每次旅行最少所需要走的路徑長。

但是哲哲有一個特異功能：只要連接兩個城市之間所有的道路他都走過了，並且他在其中一個城市，他就可以瞬間移動到另一個城市(不需要走路)。

對了，他對自己的國家ck國很陌生，他一開始沒有走過任何一條路。

對！就是這樣，請你告訴哲哲每次旅行最少需要走多遠。