완전 중요한 간선

방향이 있는 플로우 그래프가 주어진다. 어떤 간선의 용량을 $1$ 줄였을 때 그래프의 최대 유량도 정확히 $1$ 줄어든다면, 그 간선을 완전 중요한 간선이라고 부른다.

그래프가 주어졌을 때, 완전 중요한 간선의 개수를 세어라.

입력은 여러 개의 테스트 케이스로 이루어진다.

첫째 줄에 테스트 케이스의 수 $K$ ($1 \le K \le 15$)가 주어진다.

각 테스트 케이스의 첫째 줄에는 정점의 수 $N$과 간선의 수 $M$ ($2 \le N \le 300$, $2 \le M \le 5{,}000$)이 주어진다. $1$번 정점이 소스(source), $N$번 정점이 싱크(sink)이다.

이어지는 $M$개의 줄에는 각각 세 정수 $f$, $t$, $b$가 주어지며, 이는 정점 $f$에서 정점 $t$로 향하는 용량 $b$ ($b < 1000$)의 간선을 뜻한다. 모든 간선 용량의 합은 $20{,}000$을 넘지 않는다.

각 테스트 케이스마다 완전 중요한 간선의 개수를 한 줄에 하나씩 출력한다.