{$M 65520,0,655360}
program tiesiami_keliai;
  { 111 u‘davinys }
  const MAX_M = 100; { maksimalus miest— skai‡ius }
  type lentele1 = array [1..MAX_M] of integer;
       lentele2 = array [1..MAX_M, 1..MAX_M] of integer;
       aibe = set of 1..MAX_M;

  procedure ivesti (var sv: lentele2; var m: integer);
  { Ťveda pradinius duomenis }
    var u, v, i, a, b, svoris, k : integer;
        f: text;
  begin
    assign (f, 'KELIAI.DAT');
    reset (f);
    readln (f, m, k);
    for u := 1 to m do
      for v := 1 to m do
         sv[u, v] := 0;
    for i := 1 to k do
      begin
        readln (f, a, b, svoris);
        sv[a, b] := sv[a, b] + svoris;
      end;
    close (f)
  end; { Ťvesti }

  procedure max_srautas (m: integer; sv: lentele2;
                         var s: lentele2);
  { randa maksimal— sraut… grafe }
    var e, { eil‚ }
        h, bakas: lentele1;  { virž–ni— aukž‡iai ir bakasildymai }
        u, galva, uodega: integer;
        virs: aibe;

    procedure inicializuoti (var h, bakas: lentele1; { aukžtis ir bakasildymas }
                             var s: lentele2 { srautas });
    { inicializuoja h, s, bakas }
      var u, v: integer;
    begin
      for u := 1 to MAX_M do
        begin
          h[u] := 0;
          bakas[u] := 0;
        end;
     for u := 1 to MAX_M do
       for v := 1 to MAX_M do
         begin
           s[u, v] := 0;
           s[v, u] := 0;
         end;
    end; { inicializuoti }

    procedure itraukti_i_eile (u: integer;  var virs: aibe;
                               var e:lentele1; var uodega: integer);
    { Ťtraukia Ť eil‚s pabaig… virž–nŠ u }
    begin
      virs := virs + [u];
      e[uodega] := u;
      if uodega = MAX_M
         then uodega := 1
         else uodega := uodega + 1;
    end; { Ťtraukti_Ť_eilŠ }

    procedure pasalinti_is_eiles (var galva: integer; var virs: aibe);
    begin
      virs := virs - [u];
      if galva = MAX_M
         then galva := 1
         else galva := galva + 1
    end; { pažalinti_iž_eil‚s }

    procedure pakelti (u: integer; { keliama virž–n‚ }
                       var h: lentele1 { virž–ni— aukž‡iai });
    { padidinamas u aukžtis }
    { vartojami global–s kintamieji m, s, sv }
      var mini, v: integer;
          galima: boolean;
    begin
      galima := true; { ar galima pakelti virž–nŠ }
      mini := 0;
      for v := 1 to m do
        if (sv[u, v] - s[u, v] > 0)
           then if (h[u] <= h[v])
                   then begin
                          if mini = 0
                             then mini := v
                             else if h[v] < h[mini]
                                     then mini := v;
                        end
                   else galima := false;
      if galima
         then h[u] := h[mini] + 1
    end; { pakelti }

    function min (x, y: integer): integer;
    begin
      if x < y
         then min := x
         else min := y
    end; { min }

    procedure paleisti (u: integer;
                        var s: lentele2; { srautai }
                        var bakas: lentele1);
    { paleid‘ia virž–n‚s u bake esantŤ sraut… }
    { vartojami global–s kintamieji m, h, sv, e, uodega }
      var v, kiekis: integer;
    begin
      for v := 1 to m do
        if (h[v] + 1 = h[u]) and (sv[u, v] - s[u, v] > 0)
           { jei v ‘emesn‚ ir Ť j… dar galima paleisti sraut… }
           then begin
                  kiekis := min (bakas[u], sv[u, v] - s[u, v]);
                  bakas[u] := bakas[u] - kiekis;
                  s[u, v] := s[u, v] + kiekis;
                  s[v, u] := -s[u, v];
                  bakas[v] := bakas[v] + kiekis;
                  if (bakas[v] > 0) and (v <> 1)
                  then if (v <> m) and (not (v in virs))
                       then itraukti_i_eile (v, virs, e, uodega);
                end;
    end; { paleisti }

  begin
    inicializuoti (h, bakas, s);
    galva := 1; uodega := 1; { eil‚ tuž‡ia }
    virs := [];
    h[1] := m; { pradin‚s virž–n‚s aukžtis }
    { paleid‘iame sraut… iž pradin‚s virž–n‚s }
    for u := 1 to m do
      if sv[1, u] > 0
         then begin
                s[1, u] :=  sv[1, u];
                s[u, 1] := -sv[1, u];
                bakas[u] := sv[1, u];
                if u <> m
                   then itraukti_i_eile (u, virs, e, uodega);
              end;
    while virs <> [] do
      begin
        u := e[galva];
        pasalinti_is_eiles (galva, virs);
        while bakas[u] > 0 do
          begin
            pakelti (u, h);
            paleisti (u, s, bakas)
          end;
      end;
  end; { max_srautas }

  procedure isvesti (m: integer; s: lentele2);
  { spausdina rezultatus }
    var f: text;
        u, v: integer;
  begin
    assign (f, 'KELIAI.REZ');
    rewrite (f);
    for u := 1 to m do
      for v := 1 to m do
        if s[u, v] > 0
           then writeln (f, u, ' ', v, ' ', s[u, v]);
    close (f);
  end; { ižvesti }

  var sv, s: lentele2;
      m: integer;
begin
  ivesti (sv, m);
  max_srautas (m, sv, s);
  isvesti (m, s);
end.