import collections
import sys
import heapq
def solution(N, road, K):
graph = collections.defaultdict(list)
result = collections.defaultdict()
for i in range(1, N+1):
result[i] = 500001
result[1] = 0
for u, v, t in road:
graph[u].append((v,t))
graph[v].append((u,t))
print(graph)
Q = [(1, 0)]
dist = collections.defaultdict(int)
answer = 0
while Q:
node, time = heapq.heappop(Q)
for v, t in graph[node]:
time_update = time + t
if time_update <= K and time_update < result[v] :
result[v] = time_update
heapq.heappush(Q, (v, time_update))
print(result)
for i in result.values():
if i < 500001:
answer += 1
return answer