Paris

function W = solver(B)
W = zeros(0,4);
AllPaths = W;
OldEdges = W;

[II,JJ,AA] = find (B);
A = [II JJ AA];
Points = A(:,1:2);
%PoPoints = [Points Points];
Alfab = unique (B);
Alfab = Alfab (find(Alfab));
Score = zeros (size(Alfab));
BestScore = 0;

for ix = length (Alfab):-1:1
    Value = Alfab(ix);
    %findV = find (A(:,3)==Value);
    PV = A (A(:,3)==Value, 1:2);
    PwoV = setdiff(Points, PV, 'rows');
    OldEdges = [W; [PwoV PwoV]];
    Path = TheBest (PV, OldEdges);
    Path = OneWay (Path);
    Score(ix) = BestScore;
    if numel (Path)
        Score(ix) = Score(ix) + size(Path,1) - 2*Value;
    end
    AllPaths = [W; Path];
    if Score(ix) < BestScore
        W = AllPaths;
        BestScore = Score(ix);
    end
end
return

function Best = TheBest (PV, OE)
    Total = size (PV, 1);
    if Total > 1
        PV = sortrows (PV);
        P1P2 = Nearest (PV, OE);
        P1 = P1P2 (1,:);
        P2 = P1P2 (2,:);
        Diffe = P2 - P1;
        Best2 = zeros (sum(abs(Diffe))-1, 2);
        Maxiy = abs (Diffe(1));
        for iy = 1:Maxiy    % but Diffe(1) >= 0 always
            Best2 (iy, :) = [P1(1)+sign(Diffe(1))*iy P1(2)];
        end
        for iz = Maxiy+1:size(Best2,1)
            Best2 (iz, :) = [P2(1) P1(2)+sign(Diffe(2))*(iz-Maxiy)];
        end
        Best = [[P1; Best2] [Best2; P2]];
        if ~Testate (Best, OE), Best = zeros (0,4);
        end
    else Best = zeros (0,4);
    end
return

function Couple = Nearest (PV, OE)  % I'm not using OE at the moment
    Total = size (PV, 1);
    Diffe = repmat (inf, Total-1, 3);
    for ix = 1:Total-1
        for iy = 1:min(ix,Total-ix)
            [D,Pos] = min (sum( abs (diff(PV (iy:ix:end,:))' )));
            if D < sum (abs (Diffe (ix, 1:2)))
                Diffe (ix, 1:2) = PV (iy+Pos*ix,:) - PV (iy+(Pos-1)*ix,:);
                Diffe (ix, 3) = iy+Pos*ix;  % the second
            end
        end
    end
    [D,ix] = min (sum (abs (Diffe (:, 1:2))'));
    Couple = [PV(Diffe (ix, 3) - ix, :); PV(Diffe (ix, 3), :)];
return

function OK = Testate (NE, OE)
    OE2 = [OE(:,1:2); OE(:,3:4)];
    NE2 = [NE(:,1:2); NE(:,3:4)];
    if numel (intersect (NE2, OE2, 'rows')), OK = 0;
    else OK = 1; end
return

function Pnew = OneWay (P)
    P13 = sort (P(:,1:2:end), 2);
    P24 = sort (P(:,2:2:end), 2);
    Pnew = [P13(:,1) P24(:,1) P13(:,2) P24(:,2)];
    Pnew = unique (Pnew, 'rows');
return