type void struct {
}

type Node struct {
    val   int
    in    int
    out   int
    edges []*Edge
    nexts []*Node
}

type Edge struct {
    from   *Node
    to     *Node
    weitht int
}

type Graph struct {
    nodes map[int]*Node
    edges map[*Edge]void
}

func NewGraph(arr [][]int) *Graph {
    graph := Graph{nodes: map[int]*Node{}, edges: map[*Edge]void{}}
    for i := 0; i < len(arr); i++ {
        from := arr[i][0]
        to := arr[i][1]
        weight := arr[i][2]
        // init node
        if _, exist := graph.nodes[from]; !exist {
            graph.nodes[from] = &Node{val: from}
        }
        if _, exist := graph.nodes[to]; !exist {
            graph.nodes[to] = &Node{val: to}
        }
        fromNode := graph.nodes[from]
        toNode := graph.nodes[to]
        edge := &Edge{from: fromNode, to: toNode, weitht: weight}
        fromNode.out++
        toNode.in++
        fromNode.nexts = append(fromNode.nexts, toNode)

        fromNode.edges = append(fromNode.edges, edge)
        graph.edges[edge] = void{}
    }
    return &graph
}

func bfs(node *Node) {
    fmt.Println(node)
    if node == nil {
        return
    }
    queue := make([]*Node, 0, 32)
    set := make(map[*Node]void)
    queue = append(queue, node)
    set[node] = void{}
    var cur *Node
    for len(queue) != 0 {
        cur = queue[0]
        queue = queue[1:]
        fmt.Println(cur.val)
        for _, son := range cur.nexts {
            if _, exist := set[son]; !exist {
                queue = append(queue, son)
                set[son] = void{}
            }
        }
    }
}

func dfs(node *Node) {
    if node == nil {
        return
    }
    stack := make([]*Node, 0, 32)
    set := make(map[*Node]void)
    stack = append(stack, node)
    set[node] = void{}
    fmt.Println(node.val)
    for len(stack) != 0 {
        cur := stack[len(stack)-1]
        stack = stack[0 : len(stack)-1]
        for _, next := range cur.nexts {
            if _, exist := set[next]; !exist {
                stack = append(stack, cur)
                stack = append(stack, next)
                set[next] = void{}
                fmt.Println(next.val)
                break
            }
        }
    }
}

func sortedTopology(graph Graph) []*Node {
    inMap := make(map[*Node]int, 32)
    zeroQueue := make([]*Node, 0, 32)
    for _, node := range graph.nodes {
        inMap[node] = node.in
        if node.in == 0 {
            zeroQueue = append(zeroQueue, node)
        }
    }
    result := make([]*Node, 0, 32)
    for len(zeroQueue) != 0 {
        cur := zeroQueue[0]
        zeroQueue = zeroQueue[1:]
        result = append(result, cur)
        for _, next := range cur.nexts {
            inMap[next] = inMap[next] - 1
            if inMap[next] == 0 {
                zeroQueue = append(zeroQueue, next)
            }
        }
    }
    return result
}


type Edges []*Edge

func (p Edges) Len() int           { return len(p) }
func (p Edges) Less(i, j int) bool { return p[i].weitht < p[j].weitht }
func (p Edges) Swap(i, j int)      { p[i], p[j] = p[j], p[i] }

func (p *Edges) Push(x interface{}) {
    *p = append(*p, x.(*Edge))
}

func (p *Edges) Pop() interface{} {
    old := *p
    n := len(*p)
    x := old[n-1]
    *p = old[0 : n-1]
    return x
}

type Element struct {
    node *Node
}

type UnionFindSet struct {
    elementMap map[*Node]Element
    fatherMap  map[Element]Element
    sizeMap    map[Element]int
}

func (u *UnionFindSet) createUnionFindSet(nodes map[int]*Node) {
    u.elementMap = make(map[*Node]Element, 32)
    // key  某个元素  value 该元素的父
    u.fatherMap = make(map[Element]Element, 32)
    // key 某个集合的代表元素   value 该集合的大小
    u.sizeMap = make(map[Element]int, 32)
    for _, v := range nodes {
        element := Element{node: v}
        u.elementMap[v] = element
        u.fatherMap[element] = element
        u.sizeMap[element] = 1
    }
}

func (u *UnionFindSet) findHead(element Element) Element {
    path := make([]Element, 0, 32)
    for element != u.fatherMap[element] {
        path = append(path, element)
        element = u.fatherMap[element]
    }
    for i := 0; i < len(path); i++ {
        u.fatherMap[path[i]] = element
    }
    return element
}

func (u *UnionFindSet) isSameSet(a, b *Node) bool {
    if _, exist := u.elementMap[a]; exist {
        if _, exist := u.elementMap[b]; exist {
            if u.findHead(u.elementMap[a]) == u.findHead(u.elementMap[b]) {
                return true
            }
        }
    }
    return false
}

func (u *UnionFindSet) union(a, b *Node) {
    if _, exist := u.elementMap[a]; exist {
        if _, exist := u.elementMap[b]; exist {
            aF := u.findHead(u.elementMap[a])
            bF := u.findHead(u.elementMap[b])
            if aF != bF {
                big := bF
                small := aF
                if u.sizeMap[aF] >= u.sizeMap[bF] {
                    big = aF
                    small = bF
                }
                u.fatherMap[small] = big
                u.sizeMap[big] = u.sizeMap[big] + u.sizeMap[small]
                delete(u.sizeMap, small)
            }
        }
    }
}

// kruskalMST
func kruskalMST(graph *Graph) []Edge {
    var u UnionFindSet
    u.createUnionFindSet(graph.nodes)
    var edges Edges
    heap.Init(&edges)
    for edge, _ := range graph.edges {
        heap.Push(&edges, edge)
    }
    result := make([]Edge, 0, 32)
    for edges.Len() > 0 {
        edge := heap.Pop(&edges).(*Edge)
        if !u.isSameSet(edge.from, edge.to) {
            result = append(result, *edge)
            u.union(edge.from, edge.to)
        }
    }
    return result
}

func prim(graph *Graph) []*Edge {
    var edges Edges
    heap.Init(&edges)
    set := make(map[*Node]void, 32)
    result := make([]*Edge, 0, 32)
    for _, node := range graph.nodes {
        if _, exist := set[node]; !exist {
            set[node] = void{}
            for _, edge := range node.edges {
                heap.Push(&edges, edge)
            }
            for edges.Len() != 0 {
                edge := heap.Pop(&edges)
                toNode := edge.(*Edge).to
                if _, exist := set[toNode]; !exist {
                    set[toNode] = void{}
                    result = append(result, edge.(*Edge))
                    for _, curEdge := range toNode.edges {
                        heap.Push(&edges, curEdge)
                    }
                }
            }
        }
        break
    }
    return result
}