#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<string.h>
#include<assert.h>
#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

int N, M;
int edge[20][20]; /* edge[i][j] = dist of edge connecting the i-th and j-th nodes. If there are no edge, then edge[i][j] = -1 */
int opt, res; /* opt = the length of shortest paths, res = the number of paths whose length is opt */

/*
  dfs = depth first search
  now  denotes the current node (node numbered from 0 to N-1, in this code)
  dist denotes the current moved distance
  the i-th bit of mask is 1 if and only if Tomya already visited the node i
*/
void dfs(int now, int dist, int mask){
  int i,j,k;
  
  if(dist > opt) return;
  if(now == N-1){
    if(opt > dist) opt = dist, res = 0;
    res++;
    return;
  }

  rep(i,N) if(!(mask&1<<i)) if(edge[now][i] >= 0)
    dfs(i, dist+edge[now][i], mask|(1<<i));
}

int main(){
  int i,j,k;
  int T;

  assert( scanf("%d",&T)==1 );
  while(T--){
    assert( scanf("%d%d",&N,&M)==2 );
    assert( 2<=N && N<=10 && M > 0 );
    rep(i,N) rep(j,N) edge[i][j] = -1;

    while(M--){
      assert( scanf("%d%d%d",&i,&j,&k)==3 );
      assert( i!=j && 1<=i && i<=N && 1<=j && j<=N );
      assert( 1 <= k && k <= 10 );
      i--; j--;
      assert( edge[i][j] == -1 );
      edge[i][j] = edge[j][i] = k;
    }

    opt = 1000000000; res = 0;
    dfs(0, 0, 1);
    assert( res > 0 );
    printf("%d\n",res);
  }

  return 0;
}