#include <iostream>

#include <ios>

#include <iomanip>

#include <functional>

#include <algorithm>

#include <vector>

#include <sstream>

#include <list>

#include <queue>

#include <deque>

#include <stack>

#include <string>

#include <set>

#include <map>

#include <cstdio>

#include <cstdlib>

#include <cctype>

#include <cmath>

#include <cstring>

#include <climits>

using namespace std;

#define XINF INT_MAX

#define INF 1<<30

#define MAXN 1000+10

#define eps 1e-8

#define zero(a) fabs(a)<eps

#define sqr(a) ((a)*(a))

#define MP(X,Y) make_pair(X,Y)

#define PB(X) push_back(X)

#define PF(X) push_front(X)

#define REP(X,N) for(int X=0;X<N;X++)

#define REP2(X,L,R) for(int X=L;X<=R;X++)

#define DEP(X,R,L) for(int X=R;X>=L;X--)

#define CLR(A,X) memset(A,X,sizeof(A))

#define IT iterator

#define PI  acos(-1.0)

#define test puts("OK");

#define _ ios_base::sync_with_stdio(0);cin.tie(0);

typedef long long ll;

typedef pair<int,int> PII;

typedef priority_queue<int,vector<int>,greater<int> > PQI;

typedef vector<PII> VII;

typedef vector<int> VI;

#define X first

#define Y second

int V,E;

VII G2[MAXN];

int d[MAXN];

void dijkstra(int s)

{

    priority_queue<PII,VII,greater<PII> > Q;

    fill(d,d+V,INF);

    d[s]=;

    Q.push(MP(d[s],s));

    while(!Q.empty())

    {

        PII p=Q.top();Q.pop();

        int v=p.Y;

        if(d[v]<p.X)

            continue;

        REP(i,G2[v].size())

        {

            PII e=G2[v][i];

            if(d[e.X]>d[v]+e.Y)

            {

                d[e.X]=d[v]+e.Y;

                Q.push(MP(d[e.X],e.X));

            }

        }

    }

}

struct edge

{

    int to;    //终点

    int cap;   //容量

    int rev;   //反向边

    edge(int t,int c,int r){to=t;cap=c;rev=r;}

};

vector<edge> G[MAXN];   //存图

int level[MAXN];        //顶点到源点的距离标号

int iter[MAXN];         //当前弧，在其之前的边已经没有用了

int S,T;

void add_edge(int from,int to,int cap)

{

    edge e1(to,cap,G[to].size());

    G[from].PB(e1);

    edge e2(from,,G[from].size()-);

    G[to].PB(e2);

}

//通过BFS计算从源点出发的距离标号

void bfs(int s)

{

    CLR(level,-);

    queue<int> Q;

    level[s]=;

    Q.push(s);

    while(!Q.empty())

    {

        int v=Q.front();

        Q.pop();

        REP(i,G[v].size())

        {

            edge &e=G[v][i];

            if(e.cap> && level[e.to]<)

            {

                level[e.to]=level[v]+;

                Q.push(e.to);

            }

        }

    }

}

int dfs(int v,int t,int f)

{

    if(v==t)

        return f;

    for(int &i=iter[v];i<G[v].size();i++)

    {

        edge &e=G[v][i];

        if(e.cap> && level[v]<level[e.to])

        {

            int d=dfs(e.to,t,min(f,e.cap));

            if(d>)

            {

                e.cap-=d;

                G[e.to][e.rev].cap+=d;

                return d;

            }

        }

    }

    return ;

}

int max_flow(int s,int t)

{

    int flow=;

    while()

    {

        bfs(s);

        if(level[t]<)

            return flow;

        CLR(iter,);

        int f;

        while((f=dfs(s,t,INF))>)

            flow+=f;

    }

}

int main()

{_

    int P;

    scanf("%d",&P);

    while(P--)

    {

        CLR(G,);CLR(G2,);

        scanf("%d%d",&V,&E);

        REP(i,E)

        {

            int u,v,c;

            scanf("%d%d%d",&u,&v,&c);

            u--;v--;

            if(u!=v)

                G2[u].PB(MP(v,c));

        }

        scanf("%d%d",&S,&T);

        S--;T--;

        dijkstra(S);

        if(d[T]==INF)

        {

            printf("0\n");

            continue;

        }

        REP(v,V)

        {

            REP(i,G2[v].size())

            {

                PII e=G2[v][i];

                int u=e.X,cost=e.Y;

                if(d[u]-d[v]==cost)

                    add_edge(v,u,);

            }

        }

        printf("%d\n",max_flow(S,T));

    }

    return ;

}