题目背景

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

根据惯例，网络流题不允许卡 Dinic/ISAP，但可以卡 EK，本题数据严格遵循上述条约。

题目描述

给定一个 $n+1$ 个点 $m$ 条边的无向连通图，编号 $0\sim n$，多次询问两点之间的最小割。

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

输入格式

第一行两个数 $n,m$。

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

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

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

输出格式

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

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

3
4
4

提示

保证 $1\le n\leq 500$，$0\le m\leq 1500$，$0\le Q\leq 10^5$，$0\leq w\leq 10^4$，$u\neq v$。