program P2091;
var
  dist:array[1..15,1..15] of longint;
  mi:array[1..20] of longint;
  dp:array[0..15,0..1024,0..1024] of longint;
  ans,n,m,i,s,t,v,max0,c:longint;
 
procedure init;
var
  i:longint;
begin
  mi[1]:=1;
  for i:=2 to 20 do
    mi[i]:=mi[i-1] shl 1;
end;
 
function min(u,v:longint):longint;
begin
  if u<v then exit(u)
         else exit(v);
end;
 
procedure solve;
var
  i,j,k,u,cnt,l1,l2,l:longint;
begin
  fillchar(dp,sizeof(dp),$6F);
  dp[0,0,0]:=0;
  for i:=0 to n-1 do
    for j:=0 to mi[i+1]-1 do
      for k:=0 to mi[i+1]-1 do
      begin
        if dp[i,j,k]=max0 then continue;
        dp[i+1,j+mi[i+1],k+mi[i+1]]:=min(dp[i+1,j+mi[i+1],k+mi[i+1]],dp[i,j,k]+c);
        for l:=1 to i do
          if ((j shr (l-1)) and 1=1) and (dist[l,i+1]<>max0) then
            dp[i+1,j-mi[l]+mi[i+1],k]:=min(dp[i+1,j-mi[l]+mi[i+1],k],dp[i,j,k]+dist[l,i+1]);
        for l:=1 to i do
          if ((k shr (l-1)) and 1=1) and (dist[i+1,l]<>max0) then
            dp[i+1,j,k-mi[l]+mi[i+1]]:=min(dp[i+1,j,k-mi[l]+mi[i+1]],dp[i,j,k]+dist[i+1,l]);
        for l1:=1 to i do
        begin
          if (j shr (l1-1)) and 1=0 then continue;
          for l2:=1 to i do
          begin
            if l1=l2 then continue;
            if (k shr (l2-1)) and 1=0 then continue;
            if dist[l1,i+1]=max0 then continue;
            if dist[i+1,l2]=max0 then continue;
            dp[i+1,j-mi[l1],k-mi[l2]]:=min(dp[i+1,j-mi[l1],k-mi[l2]],dp[i,j,k]+dist[l1,i+1]+dist[i+1,l2]-c);
          end;
        end;
      end;
  ans:=maxlongint;
  for j:=0 to mi[n+1]-1 do
    for k:=0 to mi[n+1]-1 do
      if ans>dp[n,j,k] then ans:=dp[n,j,k];
  writeln(ans);
end;
 
begin
  assign(input,'asm_lis.in.in');assign(output,'asm_lis.in.out');
  reset(input);rewrite(output);
  readln(n,m,c);
  fillchar(dist,sizeof(dist),$6F);
  fillchar(max0,sizeof(max0),$6F);
  init;
  for i:=1 to m do
  begin
    readln(s,t,v);
    if v<dist[s,t] then dist[s,t]:=v;
  end;
  solve;
  close(input);close(output);
end.