BOJ - 16167 - A Great Way

import sys
from collections import deque

def BFS(result, graph, N):
    dq = deque()
    dq.append(1)

    while dq:
        current = dq.popleft()
        for i in range(len(graph[current])):
            neigh = graph[current][i][0]
            neighDist = graph[current][i][1]

            if result[neigh][0] == result[current][0] + neighDist:
                if result[neigh][1] > result[current][1] + 1:
                    result[neigh][1] = result[current][1] + 1
                    dq.append(neigh)

            if result[neigh][0] > result[current][0] + neighDist:
                result[neigh][0] = result[current][0] + neighDist
                result[neigh][1] = result[current][1] + 1
                dq.append(neigh)

def solution():
    N, R = map(int, sys.stdin.readline().split())
    graph = [[] for _ in range(N+1)]
    for _ in range(R):
        a, b, c, d, e = map(int, sys.stdin.readline().split())
        if e > 10: c += ((e - 10) * d)
        graph[a].append((b, c))

    result = [[1e9, 1e9] for _ in range(N+1)]
    result[1][0] = 0
    result[1][1] = 1
    BFS(result, graph, N)

    if result[N][0] == 1e9: print("It is not a great way.")
    else: print(result[N][0], result[N][1])

solution()

https://www.acmicpc.net/problem/16167