题目背景

模板题。做本题之前请确保你会Dinic或ISAP。如果你乱搞过了我请你抽烟

根据相关法律法规，网络流题不允许卡Dinic/ISAP，但可以卡EK，本题数据严格遵循上述条约

题目描述

给定一个$n$个点$m$条边的无向连通图，多次询问两点之间的最小割

两点间的最小割是这样定义的：原图的每条边有一个割断它的代价，你需要用最小的代价使得这两个点不连通

输入格式

第一行两个数$n,m$

接下来$m$行，每行$3$个数$u,v,w$，表示有一条连接$u$与$v$的无向边，割断它的代价为$w$

接下来这一行有一个整数$Q$，表示询问次数

接下来$Q$行，每行两个数$u,v$，你需要求出$u$与$v$之间的最小割

注意：因为数据有误，给定图的真实点数应该是$n+1$个，编号为$0$到$n$

输出格式

输出共$Q$行，每行一个整数对应询问的答案

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

3
4
4

提示

$n\leq 500,\quad m\leq 1500,\quad Q\leq 10^5,\quad 0\leq w\leq 10^4$