import Foundation

func solution(_ N:Int, _ road:[[Int]], _ k:Int) -> Int {
    var answer = 0
    var dist = Array(repeating: Int.max, count: N + 1)
    var visited = Array(repeating: false, count: N + 1)
    var dict = [Int: [[Int]]]()
    dist[1] = 0
    
    for r in road {
        var t1 = dict[r[0]] != nil ? dict[r[0]]! : [[Int]]()
        var t2 = dict[r[1]] != nil ? dict[r[1]]! : [[Int]]()
        t1.append([r[1], r[2]])
        t2.append([r[0], r[2]])
        dict[r[0]] = t1
        dict[r[1]] = t2
    }
    
    var pq: [Int] = [1]
    while !pq.isEmpty {
        pq.sort {
            dist[$0] < dist[$1]
        }
        let top = pq.removeLast()
				visited[top] = true
        for a in dict[top]! {
            let next = a[0] 
            let topToNextDist = a[1]
            if !visited[next] {
                if topToNextDist + dist[top] < dist[next] {
                    dist[next] = topToNextDist + dist[top]
                    pq.append(next)
                }
            }
        }
    }

    return dist.filter { $0 <= k }.count
}