Concursul "Urmasii lui Moisil" 2002

Clasele XI-XII

Problema 2- LOC

Elevii de la Liceul de Informatica vor sa îsi aleaga un loc de întâlnire. Ei au luat harta orasului Iasi si au marcat punctele culturale interesante (Casa Pogor, Bolta Rece, etc), apoi le-au numerotat de la 1 la N, Liceul de Informatica fiind numerotat 0. Între oricare doua puncte culturale exista cel mult o strada, care poate fi parcursa în ambele sensuri.
Pentru a avea cât mai multe variante de a evita întâlniri nedorite, elevii au hotarât sa aleaga drept loc de întâlnire un punct pentru care exista un numar maxim de drumuri de lungime minima care pleaca de la liceu.

Cerinta
Scrieti un program care sa aleaga un loc de întâlnire pentru elevii de la Liceul de Informatica.

Date de intrare
Fisierul de intrare LOC.IN contine

LOC.IN Semnificatie
N
m
x1 y1 L1
x2 y2 L2
...
xm ym Lm
 - numarul de puncte culturale interesante
- numarul de strazi
- exista strada între punctul x1 si punctul y1 de lungime L1
- exista strada între punctul x2 si punctul y2 de lungime L2
...
- exista strada între punctul xm si punctul ym de lungime Lm

Date de iesire
Fisierul de iesire LOC.OUT contine:

LOC.OUT Semnificatie
p
nrmax
dmin
 - locul de întâlnire ales
- numarul de drumuri de lungime minima de la liceul de informatica pâna la locul de întâlnire
- distanta minima de la liceu pâna la locul de întâlnire

Restrictii
- N<=100
- xi, yi in {0,1,...,N}, orice i din {1,2,...,m}
- Li numere naturale, 0<Li<10000, pentru orice i din{1,2,...,m}

Exemplu

LOC.IN LOC.OUT
4
6
0 1 10
0 4 40
1 2 10
2 3 10
1 4 30
2 4 20
 4
3
40

Timp maxim de executie: 1 secunda/test

Observatie
Daca exista mai multe solutii, se va determina una singura.