Packet Routing

Interview

Time limit1sMemory limit128 MB

Summary
Given a tree with weighted edges connecting N computers, compute the travel time along the unique path between each query pair of computers.
Level

Medium4 of 10

Topics
Tree, DFS, Graph, Implementation
Solved
No attempts yet

Problem

The date is October 29th, 1969. Today, scientists at UCLA made history by exchanging data between two computers over a network. The transmission wasn't very spectacular: only the first two letters of the word login were received before the system crashed. Nevertheless, the researchers are beginning to design larger computer networks, and they need your help.

A computer network is a collection of NN (2≤N≤100)(2 \le N \le 100) computers and WW wires. The computers are identified by the numbers 1,2,…,N1, 2, \dots, N. Each wire connects exactly two computers, allowing data packets to flow in both directions between them. The wires are placed so that a packet can be sent (directly or indirectly through other computers) between every pair of computers. In fact, the placement of the wires has been optimized so that there is exactly one path between every pair of computers. If a packet travels along several wires to get from the source computer to the destination computer, the time needed to travel this path is the sum of the times required to travel each individual wire. Write a program that, given a pair of distinct computers, computes the time needed for a packet to travel between them.

Input

The first line contains three positive integers NN, WW, and PP.

For each wire, a line follows giving the identification numbers of the two computers it connects, and an integer between 11 and 500500 giving the time required for a packet to travel along that wire.

PP (1≤P≤10 000)(1 \le P \le 10\,000) is the number of packets that must be sent. For each packet, a line follows giving the identification numbers of the packet's source and destination computers.

Output

For each packet, find the route through the network from the source computer to the destination computer, and output the travel time of that route on a single line.

Examples6

  1. Example 1

    Input
    3 2 3
1 2 100
2 3 150
2 1
2 3
1 3
    Expected output
    100
150
250

  2. Example 2

    Input
    2 1 1
1 2 500
1 2
    Expected output
    500

  3. Example 3

    Input
    2 1 2
2 1 1
1 2
2 1
    Expected output
    1
1

  4. Example 4

    Input
    5 4 4
1 2 10
1 3 20
1 4 30
1 5 40
2 3
4 5
2 5
5 2
    Expected output
    30
70
50
50

  5. Example 5

    Input
    7 6 4
1 2 5
1 3 7
2 4 3
2 5 8
3 6 2
3 7 9
4 7
5 6
4 5
6 7
    Expected output
    24
22
11
11

  6. Example 6

    Input
    5 4 4
1 2 100
2 3 200
3 4 300
4 5 400
1 5
1 2
3 5
5 1
    Expected output
    1000
100
700
1000