Problem
Para prepararse para la Olimpiada de Informática, el alcalde decidió proporcionar a todas las escuelas de la ciudad un suministro de energía confiable. Para hacer esto, es necesario conducir una línea eléctrica desde una fuente alternativa de electricidad “Maibuttya” a una de las escuelas de la ciudad (no importa cuál), así como para conectar algunas escuelas entre sí mediante líneas eléctricas.
Se considera que una escuela tiene un suministro de energía confiable si está conectada directamente a la fuente de Maibutcha, o a una de esas escuelas que tiene un suministro de energía confiable.
Se conoce el costo de conexión entre algunos pares de escuelas. El alcalde de la ciudad decidió elegir uno de los dos esquemas de suministro de energía más económicos (el costo del esquema es igual a la suma de los costos de conectar pares de escuelas).
Escriba un programa que calcule el costo de los dos esquemas alternativos de suministro de energía más rentables para las escuelas.
Entrada
La primera línea del archivo de entrada contiene dos números naturales separados por un espacio: N (3 <= N <= 100), el número de escuelas de la ciudad y M – el número de conexiones posibles entre ellos. Cada una de las siguientes líneas M contiene tres números: Ai, Bi , Ci, separados por espacios, donde Ci - coste del tendido de una línea eléctrica (1 <= Ci <= 300) de la escuela Ai a la escuela Bi< /sub > (i=1,2,…,N).
Salida
La única línea del archivo de salida debe contener dos números naturales S1 y S2 separados por un espacio – los dos costes de circuito más bajos (S1 <= S2). S1=S2 si y solo si hay varios esquemas de suministro de energía confiables de menor costo.
Se garantiza que existen dos esquemas diferentes de suministro de energía confiable para los datos de entrada.
Ejemplos
| # |
Entrada |
Salida |
| 1 |
5 8
1 3 75
3 4 51
2 4 19
3 2 95
2 5 42
5 4 31
1 2 9
3 5 66
|
110 121 |