1775: 交通查询系统

众所周知，交通情况是大家在日常生活中比较关心的问题。一条道路所允许的最大同时平行车辆数称为这条道路的最大吞吐量，我们假定这里都是双向道路。而我们经常要想知道两个站之间的最大总吞吐量。

由于你的才华横溢，过于出众，于是你就被交通部任命设计这个交通部的查询软件，允许市民查询目前城市的任意两个站之间的最大总吞吐量。

输输入的第一行包括两个整数N和M，分别表示该城市的站点个数和道路的个数。

接下去有M行，每行有三个整数u、v、c（1<=u、v<=N，1<=c<=10^4），表示u和v站点之间有一条道路，且吞吐量为c。

然后一行有一个整数Q。代表市民的查询次数。

接下去有Q行，每行有两个整数s、t（1<=s、t<=N），表示市民的一个查询。

50%的数据保证N<=50,Q<=10000

100%的数据保证N<=300 和Q<=100000

对于每组查询（s、t），输出s到t的最大总吞吐量。

2 1

1 2 2

2

1 2

2 1

2

2