import heapq


def dijkstra(graph, source, target):
    """
    Finds the shortest path and shortest distance from source to target

    :param graph: Dictionary linking the vertices using list of tuples
    :param source: The vertex to start the path.
    :param target: The vertex to end the path.
    :return: shortest path and distance from source to target
    """
    INF = float('Inf')
    predecessors = {x: x for x in graph}
    distances = {x: INF for x in graph}
    distances[source] = 0
    temp = []
    heapq.heappush(temp, [source, distances[source]])

    while temp:
        u = heapq.heappop(temp)
        u_dist = u[1]
        u_idx = u[0]
        if u_dist == distances[u_idx]:
            for v in graph[u_idx]:
                v_idx = v[0]
                u2v = v[1]
                if distances[u_idx] + u2v < distances[v_idx]:
                    distances[v_idx] = distances[u_idx] + u2v
                    heapq.heappush(temp, [v_idx, distances[v_idx]])
                    predecessors[v_idx] = u_idx

    if distances[target] == INF:
        return None, None
    else:
        path = []
        vertex = target
        while True:
            path.append(str(vertex))
            if vertex == predecessors[vertex]:
                break
            vertex = predecessors[vertex]
        return path[::-1], distances[target]