PRIM_THief

package main

import (
    "fmt"
)

const INF = 1000000000

var (
    vertexCounter, edgeCounter, result, v, first, second, length int
    graph [][]int
    used []bool
    min_e []int
    sel_e []int
)

func Prim() {
    min_e[0] = 0
    for i := 0; i < vertexCounter; i++ {
        v = -1
        for j := 0; j < vertexCounter; j++ {
            if !used[j] && (v == -1 || min_e[j] < min_e[v]) {
                v = j
            }
        }
        if min_e[v] == INF {
            fmt.Println("No MST!")
            break
        }
        used[v] = true
        if sel_e[v] != -1 {
            result += min_e[v]
        }
        for to := 0; to < vertexCounter; to++ {
            if graph[v][to] < min_e[to] {
                min_e[to] = graph[v][to]
                sel_e[to] = v
            }
        }
    }
}

func ReadAndCreateGraph() {
    fmt.Scanf("%d\n%d", &vertexCounter, &edgeCounter)
    graph = make([][]int, vertexCounter)
    used = make([]bool, vertexCounter)
    min_e = make([]int, vertexCounter)
    sel_e = make([]int, vertexCounter)

    for i := 0; i < vertexCounter; i++ {
        min_e[i] = INF
        sel_e[i] = -1
        graph[i] = make([]int, vertexCounter)
        for j := 0; j < vertexCounter; j++ {
            graph[i][j] = INF
        }
    }

    for i := 0; i < edgeCounter; i++ {
        fmt.Scanf("%d %d %d", &first, &second, &length)
        graph[first][second] = length
        graph[second][first] = length
    }
}

func main() {
    ReadAndCreateGraph()
    Prim()
    fmt.Println(result)
}