#include <bits/stdc++.h>
#define N 22

using namespace std;

ifstream fin ("izvor.in");
ofstream fout ("izvor.out");

int n,m,p;
int a[N][N];
int x[N],nrsol,viz[N],nr[N];

void Citire()
{
    int x,y,i,v;
    fin>>n>>p>>m;
    memset(a,-1,sizeof(a));
    for(i=1;i<=p;i++)
    {
        fin>>x>>y>>v;
        a[x][y]=a[y][x]=v;
    }
}

bool Valid(int k)
{
    if(k==1) return 1;
    if(a[x[k-1]][x[k]]==-1) return 0;
    nr[k]=nr[k-1]+a[x[k-1]][x[k]];
    return 1;
}

inline bool SolFin(int m)
{
    if(a[x[m]][x[1]]==-1) return 0;
    if(nr[m]==0) return 0;
    ///if(nr[m]==0 && a[x[m]][[]])
    return 1;
}

void Back(int k)
{
    for(int i=1;i<=n;i++)
        if(!viz[i]){
            x[k]=i;
            viz[i]=1;
            if(Valid(k))
            if(k==m) {
                if(SolFin(m)) nrsol++;
            }
            else Back(k+1);
            viz[i]=0;
        }
}

int main()
{
    Citire();
    Back(1);
    fout<<nrsol;
    return 0;
}