Hello, Codeforces!

*Initially*, I intended to just generate **random graph with random weights** but later have been warned that it may have **FEW** number of shortest Path and the contestants can random one of those shortest Path and solve the problems.

(Of course it cannot be allowed to pass all the test). So I wanna ask for some *effective* algorithm to generate test for this problems. Btw I do not know how tests for such problems are generated in the pass.

If you are interested, I will specify the problems:

## Statement

There is a connected graph with $$$n$$$ vertices and $$$m$$$ edges ($$$1 \leq n \leq 10^5$$$, $$$1 \leq m \leq 10^5$$$).

There are also $$$K (1 \leq K \leq 10)$$$ pairs of vertices $$$a_i$$$ and $$$b_i (1 \leq a_i, b_i \leq n)$$$ in which: - $$$a_i$$$ is the node which the $$$i-th$$$ person lives in. - $$$b_i$$$ is the node which the $$$i-th$$$ person's office located in.

Every morning, $$$i-th$$$ goes to work form home at 7AM along the shortest path connected $$$a_i$$$ and $$$b_i$$$. However, **X** (the first person) want to walk together with one of $$$K - 1$$$ other people during his path.

Two people are considered walking together on the edges form u to v, if: - both u and v are on the both shortest path that these 2 people walking on - the time at which 2 people reach u and v is the same.

Furthermore, some of these people (except X) agree to start walking later or sooner form home so that the time X walking together with at least one of other person is as large as possible.

The target of this problems is maximizing the amount oft time X walking with one of other people during his path form home to office.

### INPUT:

- The first line contains 3 integer $$$n, m, K (1 \leq n, m \leq 10^5, 1 \leq K \leq 10)$$$
- The next m lines have the form of $$$u, v, c$$$ ($$$u$$$ and $$$v$$$ is the end of edge, $$$1 \leq c \leq 10^9$$$ is the time required to pass)
- The next K lines have the form of $$$a_i, b_i$$$ ($$$1 \leq a_i, b_i \leq n$$$)

### OUTPUT:

The largest amount of time in which X walk together with one of $$$K - 1$$$ other people.

### Example:

**INPUT:**

```
7 8 4
2 1 2
2 4 2
4 3 2
4 5 1
1 5 3
1 7 3
5 6 2
7 6 8
1 4
0 3 2
1 7 6
0 1 2
```

**OUTPUT:**

`3`