Find the earliest time an agent knows each fact

A research agent learns facts by calling tools. A tool needs all of its input facts before it can start, runs for a fixed number of seconds, and then produces one fact. The agent can run any number of tools at the same time.

Write earliest_known(known, tools) that returns the earliest second at which the agent can know each fact.

Input and output:

• known: the facts the agent knows at second 0. A fact may be listed more than once.
• tools: up to 100,000 tools, each [inputs, output, seconds]. inputs is a list of fact names, possibly empty and possibly with repeats. output is one fact name. seconds is a whole number from 0 to 1,000,000,000. The input lists hold at most 200,000 names in all.
• Fact names are non-empty strings of any characters, compared exactly.
• Return a dictionary from every fact the agent can come to know to the earliest second it can know it. Leave out facts it can never know. Key order does not matter.

Rules:

• A tool can start at any second once all its inputs are known. A tool with no inputs can start at second 0. Its output is known seconds after it starts.
• A fact in known is known from second 0.
• Tools can feed each other in loops: a fact may be needed, directly or through other tools, to produce itself.