import heapq


def plan_tasks(durations, dependencies):
    nodes = set(durations)
    if set(dependencies) - nodes:
        raise ValueError('dependencies mention an unknown task')
    if any(not isinstance(name, str) for name in nodes):
        raise ValueError('task IDs must be strings')
    if any(not isinstance(value, int) or value < 0 for value in durations.values()):
        raise ValueError('durations must be non-negative integers')
    outgoing = {node: set() for node in nodes}
    indegree = {}
    for node in nodes:
        parents = set(dependencies.get(node, ()))
        if parents - nodes:
            raise ValueError('unknown dependency for ' + node)
        indegree[node] = len(parents)
        for parent in parents:
            outgoing[parent].add(node)
    ready = [node for node in nodes if indegree[node] == 0]
    heapq.heapify(ready)
    order = []
    start = {node: 0 for node in nodes}
    finish = {}
    while ready:
        node = heapq.heappop(ready)
        order.append(node)
        finish[node] = start[node] + durations[node]
        for child in outgoing[node]:
            start[child] = max(start[child], finish[node])
            indegree[child] -= 1
            if indegree[child] == 0:
                heapq.heappush(ready, child)
    if len(order) != len(nodes):
        remaining = sorted(node for node in nodes if indegree[node])
        raise ValueError('cycle or blocked by cycle: ' + ', '.join(remaining))
    return {'order': order, 'start': start, 'finish': finish,
            'total': max(finish.values(), default=0)}


if __name__ == '__main__':
    print(plan_tasks({'fetch': 2, 'parse': 3, 'image': 4, 'publish': 1},
                     {'parse': ['fetch'], 'image': ['fetch'],
                      'publish': ['parse', 'image']}))