Din nefericire elfii trebui să ia măsuri drastice pentru a se apăra de pericolele externe.
    Ei trebuie să amplaseze pe cărările care leagă satele lor câte un străjer la fiecare cel mult 1000 de pași.
    De exemplu, pentru o cărare care are lungimea de 24500 de pași vor fi necesari 25 de străjeri care să o păzească.
    Pentru ca numărul total al străjerilor să fie cât mai mic ei vor distruge anumite cărări astfel încât să rămână doar cele care sunt păzite.
    Evident, cărările care rămân sunt alese astfel încât să se poată călători între oricare două sate ale elfilor.
    Cele n sate ale elfilor sunt identificate prin numere cuprinse între 1 și n.

Fișierul de intrare INPUT.TXT conține pe prima linie numărul n al satelor elfilor.
    Pe cea de-a doua linie a fișierului se află numărul total m al cărărilor dintre sate.
    Fiecare dintre următoarele m linii conține câte trei numere întregi, separate prin câte un spațiu. Primele două identifică două sate care sunt unite printr-o cărare, iar al treilea indică lungimea (exprimată în pași) a cărării.

Fișierul de ieșire OUTPUT.TXT trebuie să conțină pe prima linie numărul total al străjerilor necesari.
    Fiecare dintre următoarele m linii va conține câte două numere întregi și un caracter.
    Cele două numere vor indica satele unite de o cărare, iar caracterul va indica dacă acea cărare va fi păzită sau distrusă.
    Pentru cărările păzite caracterul va fi P, iar pentru cele distruse caracterul va fi D.

  • numărul satelor elfilor este cuprins între 1 și 100;
  • numărul cărărilor dintre sate este cuprins între 1 și 1000;
  • lungimea unei cărări este cuprinsă între 500 și 10000000 de pași;
  • înainte de distrugerea anumitor cărări, există posibilitatea de a se ajunge dintr-un sat al elfilor la oricare altul;
  • pe cărări se poate circula în ambele sensuri;
  • între două sate există cel mult o cărare.


  • INPUT.TXT
    6
    11
    1 2 2500
    1 4 900
    1 5 3700
    1 6 1100
    2 3 3000
    2 4 2900
    3 4 1500
    3 5 3800
    4 5 2700
    4 6 800
    5 6 2200

    OUTPUT.TXT
    10
    1 2 D
    1 4 P
    1 5 D
    1 6 D
    2 3 P
    2 4 D
    3 4 P
    3 5 D
    4 5 P
    4 6 P
    5 6 D