type e = record j,k: word end;
var nv, {кількість вершин}
    ne, {кількість ребер}
     m, {довжина маршруту}
    i0, {індекс того, що знаємо}
    i1, {індекс того, що обчислюємо}
 j,k,l: word;

     c: array[0..1,0..9] of word;
     b: array[0..99] of e;     {масив дуг}
    nb: array[0..9]  of word;  {вказівник на ae:
        дуги, що виходять з точки j відображено у
        елементах масиву з індексами від ne[j] до
                                ne[j+1]-1 включно}
     o: text;

 {Заміна значень елементів}
procedure QSort(l,r: word);
var x,y: e;
    i,j: word;
BEGIN
x:=b[l+random(r-l+1)];
i:=l; j:=r;
while i<=j do          begin
  while b[i].j<x.j do inc(i);
  while b[j].j>x.j do dec(j);
  if i<=j then         begin
    y:=b[i];
       b[i]:=b[j];
             b[j]:=y;
    inc(i);
    dec(j)           end end;
if l<j then qsort(l,j);
if i<r then qsort(i,r);
END;
BEGIN
assign(o,'input.txt');
reset(o);
readln(o,nv,ne,m);
l:=0;
for l:=0 to ne-1 do
begin
  read(o,j,k);
  b[2*l].j:=j;
  b[2*l].k:=k;
  b[2*l+1].j:=k;
  b[2*l+1].k:=j;
end;
close(o);
randomize;
qsort(0,2*ne-1);
nb[0]:=0;

j:=1;
for l:=1 to 2*ne-1 do if (b[l].j=j) then
begin
  nb[j]:=l;
  inc(j);
end;
nb[nv]:=2*ne;
for l:=1 to nv-1 do c[0,l]:=0;
c[0,0]:=1;
i0:=0;
i1:=1;
// writeln('OK!'); halt;

for l:=0 to m-1 do
begin
  for k:=0 to nv-1 do
  begin
    c[i1,k]:=0;
    for j:=nb[k] to nb[k+1]-1 do c[i1,k]:=c[i1,k]+c[i0,b[j].k];
  end;
  i0:=1-i0;
  i1:=1-i1;
end;
assign(o,'output.txt');
rewrite(o);
writeln(o,c[i0][nv-1]);
close(o);
END.