wangyisong1996 had a small sapling, but unfortunately, it withered due to desertification. Just as wangyisong1996 was overcome with grief, a cactus grew out of the sand.

An undirected connected graph is called a cactus if every edge belongs to at most one simple cycle. A simple cycle is a cycle that does not pass through any node more than once.

There is a cactus with $n$ nodes, where each edge has a length $l$. (Different edges may have different lengths.)

There are $q$ sets of points, each described by two integers $u$ and $d$ ($1 \leq u \leq n$). A node $v$ is in this set if and only if the distance between node $v$ and node $u$ is at most $d$. The distance between two nodes is the length of the shortest path between them.

You are required to construct a Directed Acyclic Graph (DAG) that satisfies the following conditions:

1. The DAG has at least $n+q$ nodes, and at most $1,200,000$ nodes and $2,400,000$ edges.
2. For every edge, if it connects $u$ to $v$, then $u > n$ and $u \neq v$.
3. For every node $x$ that belongs to the $i$-th set ($1 \leq i \leq q$), there is exactly one path from the $(n+i)$-th node to the $x$-th node.
4. For every node $x$ that is in $\{ 1, 2, \dots, n\}$ but does not belong to the $i$-th set ($1 \leq i \leq q$), there is no path from the $(n+i)$-th node to the $x$-th node.

Input

The first line contains three positive integers $n, m, q$, where $n$ and $m$ represent the number of nodes and edges in the cactus, respectively.

The next $m$ lines each contain three integers $u, v, l$, representing an undirected edge between $u$ and $v$ with length $l$. It is guaranteed that $1 \leq u, v \leq n$.

The next $q$ lines each describe the $i$-th set using two integers $u, d$, where $1 \leq u \leq n$.

Output

The first line contains two non-negative integers $V, E$, representing the number of nodes and edges in your constructed DAG.

The next $E$ lines each contain two integers $u, v$, representing a directed edge from $u$ to $v$. You must ensure $1 \leq u, v \leq V$.

Examples

Input 1

10 9 5
2 1 9553
3 2 8499
4 3 5171
5 1 7123
6 3 1904
7 5 5526
8 7 5853
9 6 6635
10 8 7858
6 4981
7 14400
3 21290
4 9451
10 16609

Output 1

15 19
11 6
11 3
12 7
12 5
12 1
12 8
12 10
13 3
13 6
13 9
13 4
13 2
13 1
14 4
14 3
14 6
15 10
15 8
15 7

Constraints

For each edge, $1 \leq l \leq 10000$. For each set, $0 \leq d \leq 10^9$.

Generation method for the 2nd test case:

for i in range(2, 10001):
    addedge(i, i / 2)

Generation method for the 3rd test case:

for i in range(2, 5000):
    addedge(i, i - 1)
for i in range(5000, 10001):
    addedge(i, randint(1, i - 1))

Where range(l,r) denotes all integers in the interval $[l,r)$, and randint(l,r) returns a random integer in $[l,r]$.

addedge(u, v) adds an edge between $u$ and $v$. (As for how the edge lengths are generated, do you really think I would tell you?)