{$q+,r+,o-}
unit tools;

interface
uses
    SysUtils, Math;

const
    max_n = 1000;
    max_m = 10000;
    max_p = 10000;
    max_q = 10000;
    max_l = 100;
var
    a, b, l: array [1..max_m] of longint;
    n, m: longint;
    p5, q5, p6, q6: longint;
var
    maxq: longint = max_q;
    dl: longint = 1;

procedure generateLineSpan(nn, min, max: longint);
procedure generateRandomSpan(nn, mn, mx: longint);
procedure addRandom(nm, max: longint);
procedure shuffle();
procedure setData(_p5, _q5, _p6, _q6: longint);
procedure setRandomData();
procedure setCoolData();
procedure setLooseData();
procedure setTightData();
procedure setTightData2();
procedure output();
function addSpan(_a, _b, _l: longint): boolean;

implementation

var
    p: array [1..max_n] of longint;
    v, len, next: array [1..2 * max_m] of longint;
    start: array [1..max_n] of longint;
    cv: longint;
    z: array [1..max_n, 1..max_n] of longint;
    sl: longint;

function get(i: longint): longint;
begin
    if p[i] <> i then begin
        p[i] := get(p[i]);
    end;
    get := p[i];
end;

function join(i, j: longint): boolean;
begin
    i := get(i);
    j := get(j);
    join := i <> j;
    if i = j then exit;
    if (i < j) then begin
        p[j] := i;
    end else begin
        p[i] := j;
    end;
end;

procedure add2(a, b, l: longint);
begin
    assert(z[a][b] = 0);
//    if (z[a][b] <> 0) and (len[z[a][b]] <= l) then exit;
    
    inc(cv);
    next[cv] := start[a];
    len[cv] := l;
    v[cv] := b;

    start[a] := cv;
    z[a][b] := cv;
end;

procedure add(_a, _b, _l: longint);
begin
    assert(_l <> 0);
    inc(m);
    a[m] := _a;
    b[m] := _b;
    l[m] := _l;
end;

function addSpan(_a, _b, _l: longint): boolean;
begin
    result := join(_a, _b);
    if (result) then begin
        add(_a, _b, _l);
        add2(_a, _b, _l);
        add2(_b, _a, _l);
        sl := sl + _l;
    end;
end;

function generateRandom(mn, mx: longint): longint;
begin
    mx := min(mx, maxq - (n - m) * mn - sl);
    repeat
        result := mn + random(mx - mn + 1);
    until ((result mod mn) <= dl) or (mn - (result mod mn) <= dl);
end;

procedure generateRandomSpan(nn, mn, mx: longint);
begin
    n := nn;
    while m <> nn - 1 do begin
        //sl + (n - m) * min < max_q
        addSpan(random(nn) + 1, random(nn) + 1, generateRandom(mn, mx));
    end;
end;

procedure generateLineSpan(nn, min, max: longint);
var
    i: longint;
begin
    n := nn;
    for i := 1 to nn - 1 do begin
        addSpan(i, i + 1, generateRandom(min, max));
    end;
end;

function maxOnPath(a, b: longint): longint;
var
    u: array [1..max_n] of boolean;
    function dfs(i, l: longint): longint;
    var
        p: longint;
    begin
        result := 0;
        if u[i] then exit;
        u[i] := true;
        if i = b then begin
            result := l;
            exit;
        end;
        p := start[i];
        while p <> 0 do begin
            result := dfs(v[p], max(l, len[p]));
            if result <> 0 then break;
            p := next[p];
        end;
    end;
begin
    fillchar(u, sizeof(u), 0);
    maxOnPath := dfs(a, 1);
end;

procedure addRandom(nm, max: longint);
var
    a, b, l: longint;
begin
    while m < nm do begin
        a := random(n) + 1;
        b := random(n) + 1;
        l := maxOnPath(a, b);
        if l <= max then begin
            add(a, b, l + random(max - l + 1));
        end;        
    end;
end;

procedure shuffle();
var
    i, j, t: longint;
    pv: array [1..max_n] of longint;
begin
    for i := 1 to n do begin
        j := random(i) + 1;
        pv[i] := pv[j];
        pv[j] := i;
    end;
    for i := 1 to m do begin
        if random > 0.5 then begin
            t := b[i]; b[i] := a[i]; a[i] := t;
        end;
        a[i] := pv[a[i]];
        b[i] := pv[b[i]];
    end;
    for i := 1 to m do begin
        j := random(i) + 1;
        t := a[i]; a[i] := a[j]; a[j] := t;
        t := b[i]; b[i] := b[j]; b[j] := t;
        t := l[i]; l[i] := l[j]; l[j] := t;
    end;
end;

procedure setData(_p5, _q5, _p6, _q6: longint);
begin
    p5 := _p5;
    q5 := _q5;
    p6 := _p6;
    q6 := _q6;
//    writeln(_p5:8, _q5:8, _p6:8, _q6:8);
end;

procedure setDataRandom(p5, q5, p6, q6: longint);
begin
    if (random > 0.5) then begin
        setData(p5, q5, p6, q6);
    end else begin
        setData(p6, q6, p5, q5);
    end;
end;

procedure setRandomData();
begin
    setData(
        random(max_p) + 1,
        random(min(sl, max_q)) + 1,
        random(max_p) + 1,
        random(min(sl, max_q)) + 1
    );
end;

function w(i, j, sl: longint): double;
begin
    //w := j * (exp(10) - exp(10 * sqrt(abs(2 * i - sl) / sl)));
    w := -abs(2 * i - sl);
end;

var
    u: array [0..max_n * max_l] of boolean;

procedure getCoolInterval(var maxi, maxj: longint);
var
    i, j: longint;
begin
    fillchar(u, sizeof(u), 0);
    u[0] := true;
    for i := 1 to n - 1 do begin
        for j := sl downto l[i] do begin
            u[j] := u[j] or u[j - l[i]];
        end;
    end;
    i := 1;
    maxj := 0;
    maxi := 0;
    while i <= sl do begin
        j := 0;
        while (i <= sl) and (not u[i]) do begin
            inc(i);
            inc(j);
        end;
//        if (j > 1) then begin
//            writeln(i, ' ', j, ' ', w(i, j, sl):0:3);
//        end;
        
        if (j > 1) and (i > j + 1) and (w(i, j, sl) > w(maxi, maxj, sl)) then begin
            maxj := j;
            maxi := i;
        end;
        inc(i);
    end;
    maxi := maxi - maxj;
    dec(maxj);
    assert(maxi > 0);
    assert(maxj > 0);
    assert(not u[maxi]);
    assert(not u[maxi + maxj]);
    assert(u[maxi + maxj + 1]);
end;

procedure setCoolData();
var
    maxi, maxj: longint;
begin
    getCoolInterval(maxi, maxj);
    setRandomData();
    setDataRandom(
        p5,
        maxi + 1 + random(maxj),
        p6,
        sl - maxi + random(maxj)
    );
end;

procedure setTightData();
var
    maxi, maxj: longint;
begin
    getCoolInterval(maxi, maxj);
    setRandomData();
//    writeln(maxi, ' ', sl - maxi);
    setDataRandom(
        p5,
        maxi - 1,
        p6,
        sl - maxi + 1
    );
end;

procedure setLooseData();
var
    maxi, maxj: longint;
begin
    getCoolInterval(maxi, maxj);
    setRandomData();    
    setDataRandom(
        p5,
        maxi + maxj + 1,
        p6,
        sl - maxi - maxj
    );
end;

procedure setTightData2();
var
    maxi, maxj: longint;
begin
    getCoolInterval(maxi, maxj);
    setRandomData();
    setDataRandom(
        p5,
        maxi + maxj,
        p6,
        sl - maxi
    );
end;

procedure assertBetween(a, x, b: longint; name: string);
begin
    assert((a <= x), format('%s < %d', [name, a]));
    assert((x <= b), format('%s > %d', [name, b]));
end;

procedure output(); overload;
var
    i: longint;
begin
    assertBetween(1, n, max_n, 'n');
    assertBetween(1, m, max_m, 'm');
    assertBetween(1, p5, max_p, 'p5');
    assertBetween(1, q5, max_q, 'q5');
    assertBetween(1, p6, max_p, 'p6');
    assertBetween(1, q6, max_q, 'q6');

    writeln(n, ' ', m);

    for i := 1 to m do begin
        assertBetween(1, a[i], n, 'a');
        assertBetween(1, b[i], n, 'b');
        assertBetween(1, l[i], max_l, 'l');
        writeln(a[i], ' ', b[i], ' ', l[i]);
    end;

    writeln(p5, ' ', q5, ' ', p6, ' ', q6);
end;

var
    i: longint;
begin
    for i := 1 to max_n do begin
        p[i] := i;
    end;
end.
