PROGRAMMING:Xiangxiang's walkie talkie
In order to communicate with Lan Lan quickly at any time, Xiang Xiang arranged two walkie talkies.
Xiangxiang and Lanlan are located in $$n $$houses and $$M $$bidirectional optical cables. Each optical cable connects two houses. The signal from the walkie talkie can only be transmitted along the optical cable, and it takes $$t $$unit time to transmit the signal from one end of the optical cable to the other end.
Now Xiangxiang has to carry out $$q $$tests, choosing two houses at a time, and wants to know how long it will take for the intercom signal to pass between the two houses at least. Xiangxiang and Lanlan don't know what to do. Please help them
The $$n $$houses must be connected through optical cables, and the $$M $$optical cables have the following three types of connection:
$$a $: the optical cable does not form a ring, that is, there are only $$n-1 $$optical cables.
$$B $$: the optical cable only forms a ring, that is, the optical cable only has $$n $$.
$$C $$: * * each fiber optic cable is in only one ring**
###Input format:
The first line contains three integers separated by spaces, $$n $$, $$M $$, and $$q $$.
Next, $$M $$line has three integers, $$x $, $$y $, $$t $$in each line, indicating that there is an optical cable with a transfer time of $$t $$between house $$x $$and $$y $$.
Finally, there are two integers, $$x $$, $$y $$, in the $$q $$line, which indicates that Xiangxiang wants to know how long it takes at least for the signal to pass between $$x $$and $$y $$.
###Output format:
Output $$q $$lines, an integer for each line, indicating the result of each test.
###Input sample 1:
```in
5 4 2
1 2 1
1 3 1
2 4 1
2 5 1
3 5
2 1
```
###Output sample 1:
```out
three
one
```
###I / O sample 1 Description
First inquiry: the time from room $$3 $$to room $$1 $$is $$1 $, the time from room $$1 $$to room $$2 $$is $$1 $, the time from room $$2 $$to room $$5 $$is $$1 $, the total time is $$3 $.
Second inquiry: the time from room $$2 $$to room $$1 $$is $$1 $, and the total time is $$1 $
###Input sample 2:
```in
9 10 2
1 2 1
1 4 1
3 4 1
2 3 1
3 7 1
7 8 2
7 9 2
1 5 3
1 6 4
5 6 1
1 9
5 7
```
###Output sample 2:
```out
five
six
```
###I / O sample 2 Description
First inquiry: the time from room $$1 $$to room $$2 $$is $$1 $, the time from room $$2 $$to room $$3 $$is $$1 $, the time from room $$3 $$to room $$7 $$is $$1 $, the time from room $$7 $$to room $$9 $$is $$2 $, the total time is $$5 $.
The second inquiry: the time from room $$5 $$to room $$1 $$is $$3 $, the time from room $$1 $$to room $$4 $$is $$1 $, the time from room $$2 $$to room $$3 $$is $$1 $, the time from room $$3 $$to room $$7 $$is $$1 $, and the total time is $$6 $$.
###Input sample 3
```in
13 16 4
1 2 1
2 4 1
1 3 1
3 4 4
3 12 1
12 13 1
13 3 3
3 10 1
3 11 1
10 11 1
4 6 3
4 5 1
5 6 1
6 8 1
8 7 1
8 9 1
12 13
9 13
11 4
13 11
```
###Output sample 3
```out
one
nine
four
three
```
###Data scale and agreement
For the data of $$10 \% $, $$2 / Leq n / Leq 1000 $$, $$n-1 / Leq M / Leq 1200 $$.
$$a $$data accounts for $$30 \% $, $$m = n-1 $$.
$$B $$data accounts for $$50 \% $, $$m = n $$.
$$C $$data accounts for $$10 \% $, $$m > n $$.
For the data of $$100 \% $, $$2 / Leq n / Leq 10000 $$, $$n-1 / Leq M / Leq 12000 $$, $$q = 10000 $$, $$1 / Leq x, Y / Leq n $$, $$1 / Leq T < 32768 $$.
Note: the proportional distribution of data does not represent the proportional distribution of scores, but it can be considered as such.
answer：If there is no answer, please comment
It needs to be implemented separately for three groups of data features. For reference https://blog.csdn.net/u011056504/article/details/51519475
Xiangxiang and Lanlan are located in $$n $$houses and $$M $$bidirectional optical cables. Each optical cable connects two houses. The signal from the walkie talkie can only be transmitted along the optical cable, and it takes $$t $$unit time to transmit the signal from one end of the optical cable to the other end.
Now Xiangxiang has to carry out $$q $$tests, choosing two houses at a time, and wants to know how long it will take for the intercom signal to pass between the two houses at least. Xiangxiang and Lanlan don't know what to do. Please help them
The $$n $$houses must be connected through optical cables, and the $$M $$optical cables have the following three types of connection:
$$a $: the optical cable does not form a ring, that is, there are only $$n-1 $$optical cables.
$$B $$: the optical cable only forms a ring, that is, the optical cable only has $$n $$.
$$C $$: * * each fiber optic cable is in only one ring**
###Input format:
The first line contains three integers separated by spaces, $$n $$, $$M $$, and $$q $$.
Next, $$M $$line has three integers, $$x $, $$y $, $$t $$in each line, indicating that there is an optical cable with a transfer time of $$t $$between house $$x $$and $$y $$.
Finally, there are two integers, $$x $$, $$y $$, in the $$q $$line, which indicates that Xiangxiang wants to know how long it takes at least for the signal to pass between $$x $$and $$y $$.
###Output format:
Output $$q $$lines, an integer for each line, indicating the result of each test.
###Input sample 1:
```in
5 4 2
1 2 1
1 3 1
2 4 1
2 5 1
3 5
2 1
```
###Output sample 1:
```out
three
one
```
###I / O sample 1 Description
First inquiry: the time from room $$3 $$to room $$1 $$is $$1 $, the time from room $$1 $$to room $$2 $$is $$1 $, the time from room $$2 $$to room $$5 $$is $$1 $, the total time is $$3 $.
Second inquiry: the time from room $$2 $$to room $$1 $$is $$1 $, and the total time is $$1 $
###Input sample 2:
```in
9 10 2
1 2 1
1 4 1
3 4 1
2 3 1
3 7 1
7 8 2
7 9 2
1 5 3
1 6 4
5 6 1
1 9
5 7
```
###Output sample 2:
```out
five
six
```
###I / O sample 2 Description
First inquiry: the time from room $$1 $$to room $$2 $$is $$1 $, the time from room $$2 $$to room $$3 $$is $$1 $, the time from room $$3 $$to room $$7 $$is $$1 $, the time from room $$7 $$to room $$9 $$is $$2 $, the total time is $$5 $.
The second inquiry: the time from room $$5 $$to room $$1 $$is $$3 $, the time from room $$1 $$to room $$4 $$is $$1 $, the time from room $$2 $$to room $$3 $$is $$1 $, the time from room $$3 $$to room $$7 $$is $$1 $, and the total time is $$6 $$.
###Input sample 3
```in
13 16 4
1 2 1
2 4 1
1 3 1
3 4 4
3 12 1
12 13 1
13 3 3
3 10 1
3 11 1
10 11 1
4 6 3
4 5 1
5 6 1
6 8 1
8 7 1
8 9 1
12 13
9 13
11 4
13 11
```
###Output sample 3
```out
one
nine
four
three
```
###Data scale and agreement
For the data of $$10 \% $, $$2 / Leq n / Leq 1000 $$, $$n-1 / Leq M / Leq 1200 $$.
$$a $$data accounts for $$30 \% $, $$m = n-1 $$.
$$B $$data accounts for $$50 \% $, $$m = n $$.
$$C $$data accounts for $$10 \% $, $$m > n $$.
For the data of $$100 \% $, $$2 / Leq n / Leq 10000 $$, $$n-1 / Leq M / Leq 12000 $$, $$q = 10000 $$, $$1 / Leq x, Y / Leq n $$, $$1 / Leq T < 32768 $$.
Note: the proportional distribution of data does not represent the proportional distribution of scores, but it can be considered as such.
answer：If there is no answer, please comment
It needs to be implemented separately for three groups of data features. For reference https://blog.csdn.net/u011056504/article/details/51519475