árvore geradora
Problem
É necessário encontrar uma árvore geradora de peso mínimo em um grafo conectado.
Entrada
A primeira linha do arquivo de entrada contém dois números naturais n e m - o número de vértices e arestas do grafo, respectivamente (1≤n≤20000, 0≤m≤100000). As próximas m linhas contêm a descrição das arestas, uma por linha. O número da borda i é descrito por três números naturais bi, ei e wi - os números das extremidades da borda e seu peso, respectivamente (1≤bi,ei≤n, 0≤wi≤100000).
O gráfico está conectado.
Saída
Imprime um único inteiro - o peso da árvore geradora mínima.
| Entrada |
Saída |
|
4 4
1 2 1
2 3 2
3 4 5
4 1 4
|
7 |