task 9

package main

import (
    "bufio"
    "fmt"
    "math"
    "os"
    "strconv"
    //"github.com/pkg/profile"
)

type optic struct {
    From, To int
}

func main() {

    //defer profile.Start(profile.CPUProfile).Stop()
    in := bufio.NewReader(os.Stdin)
    out := bufio.NewWriter(os.Stdout)
    defer out.Flush()

    var t int
    fmt.Fscan(in, &t)

    for k := 0; k < t; k++ {

        var n, start int
        startVal := math.MaxInt
        fmt.Fscan(in, &n)
        points := make([]int, n)
        for i := 0; i < n; i++ {
            fmt.Fscan(in, &points[i])
            if points[i] < startVal {
                start = i
                startVal = points[i]
            }
        }

        var m int
        fmt.Fscan(in, &m)
        optics := make(map[optic]int)
        for i := 0; i < m; i++ {
            var from, to, val int
            fmt.Fscan(in, &from, &to, &val)
            optics[optic{from - 1, to - 1}] = val
            optics[optic{to - 1, from - 1}] = val
        }

        visits := make(map[int]bool)

        l := start
        cost := startVal
        for {
            visits[l] = true

            if len(visits) == n {
                break
            }

            min := math.MaxInt

            for i := range visits {
                for j := 0; j < n; j++ {

                    if !visits[j] {
                        val := points[j]
                        if v, ok := optics[optic{i, j}]; ok {
                            if v < val {
                                val = v
                            }
                        }

                        if val < min {
                            min, l = val, j
                        }
                    }
                }
            }

            cost += min
        }

        out.WriteString(strconv.Itoa(cost))
        out.WriteString("\n")

    }
}