C. Coin Master
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Jennifer is travelling to a nation with $$$N$$$ cities numbered from $$$1$$$ to $$$N$$$. There are $$$M$$$ bidirectional roads in the nation. The $$$i$$$-th road connects cities $$$A_i$$$ and $$$B_i$$$, Jennifer can travel from city $$$A_i$$$ to city $$$B_i$$$ and vice versa through the road, without paying any cost. When Jennifer passes the road for the first time (no matter which direction), she can pick up $$$C_i$$$ coins that lie on the road.

Additionally, there are $$$K$$$ pairs of bidirectional portals, the $$$i$$$-th pair connects city $$$D_i$$$ and $$$E_i$$$. Once Jennifer pays the cost of $$$P_i$$$ coins, the pair of portals is unlocked and Jennifer can travel from city $$$D_i$$$ to $$$E_i$$$ and vice versa for an unlimited number of times.

As Jennifer is a coin master who loves collecting coins, help her find out the maximum number of coins she can get at the end of her trip if she starts with $$$0$$$ coins and starts and ends in a city of her own choice.

Input

The first line contains 3 integers: $$$N$$$ $$$(1 \leq N \leq 2\times 10^5)$$$, $$$M$$$ $$$(0 \leq M \leq 5\times 10^5)$$$, and $$$K$$$ $$$(0 \leq K \leq 16)$$$.

The next $$$M$$$ lines each describe a road. The $$$i$$$-th line contains 3 integers: $$$A_i$$$, $$$B_i$$$ $$$(1 \leq A_i \lt B_i \leq N)$$$, and $$$C_i$$$ $$$(1 \leq C_i \leq 10^9)$$$, denoting the road connects city $$$A_i$$$ and $$$B_i$$$ with $$$C_i$$$ collectible coins.

The last $$$K$$$ lines each describe a pair of portals. The $$$i$$$-th line contains 3 integers: $$$D_i$$$, $$$E_i$$$ $$$(1 \leq D_i \lt E_i \leq N)$$$, and $$$P_i$$$ $$$(1 \leq P_i \leq 10^9)$$$, denoting the pair of portals connects city $$$D_i$$$ and $$$E_i$$$ and requires $$$P_i$$$ coins to unlock.

Note that there are no 2 roads or 2 pairs of portals that connect the same pair of cities, i.e. $$$(A_i, B_i) \neq (A_j, B_j)$$$ for $$$1\leq i \lt j \leq M$$$, and $$$(D_i, E_i) \neq (D_j, E_j)$$$ for $$$1\leq i \lt j \leq K$$$.

Output

The only line in the output contains the maximum number of coins Jennifer can get at the end of her trip.

Examples
Input
6 4 1
1 2 5
2 3 1
3 4 2
5 6 6
3 6 4
Output
10
Input
8 4 1
1 2 2
4 5 3
5 6 5
7 8 6
6 8 4
Output
10
Note

For the first sample test, to obtain $$$10$$$ coins at the end of her trip, Jennifer may do the following:

  • Start at city $$$1$$$ with $$$0$$$ coins initially.
  • Go to city $$$2$$$ through the $$$1$$$-st road and collect $$$5$$$ coins.
  • Go to city $$$3$$$ through the $$$2$$$-nd road and collect $$$1$$$ coins.
  • Go to city $$$4$$$ through the $$$3$$$-rd road and collect $$$2$$$ coins.
  • Go to city $$$3$$$ through the $$$3$$$-rd road, no coins can be collected as the coins are collected already.
  • Unlock the only pair of portal by paying $$$4$$$ coins.
  • Go through the unlocked portal to city $$$6$$$.
  • Go to city $$$5$$$ through the $$$4$$$-th road and collect $$$6$$$ coins.
  • End her journey with 10 coins.