#include <iostream>
#include <algorithm>
using namespace std;
#define Max_node 1001
#define Max_edge 10001
struct node 
{
	int a , b , c ;
}E[Max_edge];
int dist[Max_node][2];
int ans[Max_node][2];
int n , m ;
int S,F;
int ID[Max_node];
bool cmp(node aa , node bb )
{
	return aa.a < bb.a;
}
void init()
{
	cin >> n >> m ;
	for ( int i = 1; i <= m ; i ++ ) cin >> E[i].a >> E[i].b >> E[i].c;
	cin >> S >> F;
	sort(E+1,E+m+1,cmp);
	memset(ID,0,sizeof(ID)) ;
	for ( i = 1 ; i <= m ; i ++ )
		if (ID[E[i].a] == 0 )  ID[E[i].a]=i;
	return;
}
void dijkstra()
{
	int i  , j;
	int P[Max_node];
	memset(P,0,sizeof(P));
	for ( i = 1 ; i <= n ; i ++ ) {
		dist[i][0] =1000000000;
		dist[i][1] =1000000000;
	}
	dist[S][0] = 0;
	memset(ans,0,sizeof(ans));
	ans[S][0] = 1 ;
	for ( i = 1 ;i < n ; i ++ )
	{
		int ij ;
		int min  =  1000000000;
		for ( j = 1 ; j <= n ; j ++ )
			if (dist[j][0] < min&&!P[j] )  min  = dist[j][0],ij=j;
		P[ij] = true;
		for( j = ID[ij] ; j <= m ; j ++ )
		{
			if (E[j].a != ij ) break;
			if (dist[ij][0]+E[j].c<dist[E[j].b][0]) 
			{
				ans[E[j].b][0]=ans[ij][0];
				dist[E[j].b][0]=dist[ij][0]+E[j].c;
				continue;
			}
			if (dist[ij][0]+E[j].c==dist[E[j].b][0]) {
				ans[E[j].b][0]+=ans[ij][0];
				continue;
			}
			if (dist[ij][0]+E[j].c<dist[E[j].b][1]) {
				ans[E[j].b][1]=ans[ij][0];dist[E[j].b][1]=dist[ij][0]+E[j].c;
			}

		}
	}
	if (dist[F][0]==dist[F][1]-1) cout << ans[F][0]+ans[F][1] <<endl;
	else cout <<  ans[F][0] <<endl;
	return ;
}
int main()
{
	int t;
	cin >> t ;
while (t--)
{
	init();
	dijkstra();
}
	return 0;
}