var n,m,c,i,j,min,a,b,v,k:longint;
map:array[1..5,0..5] of longint;
cos:array[1..5,0..5] of longint;
begin
assign(input,'asm_lis.in');
reset(input);
assign(output,'asm_lis.out');
rewrite(output);
 readln(n,m,c);
 for i:=1 to m do
  begin
   readln(a,b,v);
   inc(map[a,0]);
   map[a,map[a,0]]:=b;
   cos[a,map[a,0]]:=v;
  end;
 if n=2 then
  begin
   if map[1,1]<>0 then min:=cos[1,1]+c;
   if (map[2,1]<>0) and (cos[2,1]<cos[1,1]) then min:=cos[2,1]+c;
   writeln(min);
   halt;
  end;
 if n=3 then
  begin
   for j:=1 to map[1,0] do
    for k:=1 to map[j,0] do
     if ((map[1,j]=2)and(map[j,k]=3)) or ((map[1,j]=3)and(map[j,k]=2)) and(cos[1,j]+cos[j,k]+c<min) then
     min:=cos[1,j]+cos[j,k]+c;
   for j:=1 to map[2,0] do
    for k:=1 to map[j,0] do
     if ((map[1,j]=1)and(map[j,k]=3)) or ((map[1,j]=3)and(map[j,k]=1)) and(cos[1,j]+cos[j,k]+c<min) then
     min:=cos[1,j]+cos[j,k]+c;
   for j:=1 to map[3,0] do
    for k:=1 to map[j,0] do
     if ((map[1,j]=1)and(map[j,k]=2)) or ((map[1,j]=2)and(map[j,k]=1)) and(cos[1,j]+cos[j,k]+c<min)  then
     min:=cos[1,j]+cos[j,k]+c;
  end;
 writeln(min);
 close(input);
 close(output);
end.