二人旅

ahri と teemo がうしたぷにきあ王国で観光をします。うしたぷにきあ王国には個の都市と本の道があり、任意の都市は何本かの道を通って必ず到達することができます。 また、番目の道を使うと都市と都市を距離で行き来することができて、王国に閉路はありません。 ahri は都市からスタートして都市に向かって最短経路で観光をし、 teemo は都市からスタートして都市に向かって最短経路で観光をします。

ahri と teemo は最初1人旅ですが、途中ある都市で偶然出会った時は出会った都市から都市まで2人旅で一緒に最短経路で観光します。

ahri と teemo のスタート地点となる都市の組のクエリが個与えられます。各クエリに対し、2人旅で移動する可能性のある距離のうち最大値を改行区切りで出力してください。

︙

︙

各クエリに対し、2人旅で移動する可能性のある距離のうち最大値を改行区切りで出力してください。

8 8
8 6 1
7 6 2
6 5 2
6 5 3
5 4 4
5 3 5
5 2 5
2 1 6
2 8
1 3
1 2

3
8

クエリ1では

ahri は 1→2→5→6→8 teemo は 3→5→6→8 の順番で都市を観光します。

都市5で出会った時2人旅が最長になります。 ただし、2人旅でも最短経路を通って観光するので出力は都市5から都市8の距離3になります。

クエリ2では

ahri は 1→2→5→6→8 teemo は 2→5→6→8 の順番で都市を観光します。

都市2で出会った時2人旅が最長になるので、都市2から都市8の距離8を出力します。

5 4
1 3 4
2 3 3
3 5 2
4 5 1
1 5
1 4

0

クエリ1では ahri は 1→3→5 teemo は 4→5 の順番で都市を観光します。 都市5でしか出会えないので、2人旅の最長距離は0です。

9 18
1 4 52
4 5 64
3 5 85
1 2 41
6 8 65
1 7 83
5 8 99
1 9 51
1 4 16
6 8 37
1 4 67
3 5 50
6 8 31
4 5 45
3 5 66
1 7 17
1 9 38
3 5 42
3 3
1 8
2 7
3 6

42
103
0