Problem Miguel și Primăria


Enunț

Miguel, noul primar, are nevoie de ajutor să-și plaseze optim primăria. El poate alege dintre \(N\) clădiri care sunt conectate cu \(N - 1\) drumuri cu sens unic. Dacă nu luăm în considerare orientarea drumurilor, toate clădirile sunt conectate între ele. De asemenea, fiecare drum are asociat un coeficient \(G\), numărul de utilizatori zilnici.

Primăria ar trebui să fie accesibilă de către orice altă clădire, însă acest lucru s-ar putea să nu fie posibil mereu. Astfel, Miguel este dispus să inverseze direcția unor drumuri. Fiind un primar bun căruia îi pasă de cetățeni, el vrea să inverseze drumuri astfel încât un număr minim de persoane sunt afectate de schimbări.

Miguel vrea să îi spui numărul minim de persoane afectate și indicele minim al unei clădiri pentru care s-ar obține acest număr minim.

Date de intrare

Se citesc un număr natural \(N\) (numărul de clădiri) și \(N - 1\) triplete de de numere naturale \(X, Y, C\) cu semnificația că există un drum cu sens unic între clădirile \(X\) și \(Y\), utilizat de \(C\) persoane.

Date de ieșire

Se afișează, separate printr-un spațiu, numărul minim de persoane afectate și cel mai mic indice al unei clădiri pentru care se poate obține acest număr minim.

Restricții și Precizări

  • \(2 \leq N \leq 100.000\)
  • Clădirile sunt indexate de la \(1\) la \(N\)
  • \(1 \leq X, Y \leq N\)
  • \(0 \leq C \leq 1.000.000\)

Exemplu

stdin

9
2 3 2
6 3 1
5 2 0
5 7 4
5 8 3
8 4 2
9 5 3
1 7 1

stdout

6 4

Explicație

Aceasta este reprezentarea exemplului:

Reprezentarea exemplului

Alegera clădirii 4 să fie primărie duce la numărul minim de persoane afectate: cele care folosesc drumurile \(5\to7\) și \(2\to3\).

General info

ID: 73

Upload: AlexVasiluta

Input: Console Input

Memory limit: 64MB/16MB

Time limit: 1s

Author: Popa Sebastian

Source: Miguel's Summer Challenge

Submissions

Special Submissions