Graph Operations with Latency Queries

You are given a network of hubs and a series of operations. Each operation is either to add an undirected edge between two hubs with a specified latency or to query the shortest path latency between two hubs. Initially, the network has no connections. When an edge is added using the "ADD" command, if an edge already exists between the two hubs, its latency is updated. When a query is encountered using the "QUERY" command, you must compute the minimum total latency from one specified hub to another using the available connections.

Use Dijkstra's algorithm to compute the shortest paths efficiently. If there is no path between the two hubs during a query, return -1.

Input Format: The first line contains two integers n and q which denote the number of hubs and the number of operations respectively. The next q lines each contain an operation in one of the following forms:

• ADD a b d — add or update an edge between hub a and hub b with latency d.
• QUERY a b — output the minimum latency from hub a to hub b, or -1 if no path exists.

inputFormat

The input is read from standard input (stdin) and follows this format:

n q
operation_1
operation_2
...
operation_q

Where n is the number of hubs, q is the number of operations, and each operation is either an ADD or QUERY command as described above.

outputFormat

For each QUERY operation, output the result (the minimum path latency or -1 if no path exists) on a separate line to standard output (stdout).

## sample

5 7
ADD 1 2 10
ADD 2 3 5
ADD 3 4 7
QUERY 1 4
ADD 1 4 15
ADD 4 5 1
QUERY 1 5

22
16

</p>