const inf = math.MaxInt32

func networkDelayTime(distances [][]int, n int, k int) int {
    // 格式化输入，记录i到j的距离
    distanceMap := make([][]int, n)
    for i := range distanceMap {
        distanceMap[i] = make([]int, n)
        for j := range distanceMap[i] {
            // 默认最大
            distanceMap[i][j] = inf
        }
    }
    for _, d := range distances {
        distanceMap[d[0] - 1][d[1] - 1] = d[2]
    }

    // 记录起点到其他点的最短距离
    dist := make([]int, n)
    for i := range dist {
        dist[i] = inf
    }
    dist[k - 1] = 0

    // 标记点已被访问过
    visited := make([]bool, n)

    for i := 0; i < n; i++ {
        // 寻找距离起点最近的点，第一次的话就是起点
        closest := -1
        for candicate, v := range visited {
            if !v && (closest == -1 || dist[candicate] < dist[closest]) {
                closest = candicate
            }
        }

        visited[closest] = true

        // 更新邻居节点的距离
        for ne, d := range distanceMap[closest] {
            // inf说明不是邻居节点
            if d == inf {continue}
            dist[ne] = Min(dist[ne], dist[closest] + d)
        }
    }

    ans := -inf
    for _, d := range dist {
        if d == inf {
            return -1
        }
        ans = Max(ans, d)
    }

    return ans
}

func Min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

func Max(a, b int) int {
    if a > b {
        return a
    }
    return b
}