Dans une pièce sombre, vers 23h55, Milan est assis à une table à trois pieds et commence à réfléchir aux conséquences éventuelles qu'une catastrophe nucléaire pourrait provoquer dans sa ville. En tant que maire, Milan est très bien informé de tous les faits pertinents.

Il sait que sa ville compte exactement $N$ habitants et que chaque habitant vit dans sa propre maison. Il existe des routes entre exactement $M$ paires de maisons, et pour chaque route, le temps nécessaire pour la parcourir est connu. Enfin, Milan sait dans quelles $K$ maisons se trouvent des abris antiatomiques et combien de personnes chaque abri peut accueillir. Ayant tout cela à l'esprit, la question suivante tourmente Milan : « Quel est le temps minimal nécessaire pour évacuer tous les habitants de cette ville ? » Aidez Milan à répondre à cette question.

Bien entendu, l'évacuation implique que chaque habitant finisse dans un abri antiatomique. Vous pouvez supposer que les habitants se déplacent de manière optimale (par le chemin le plus court) et que plusieurs personnes peuvent se déplacer simultanément le long d'une même route, potentiellement dans des directions différentes. Vous pouvez également supposer qu'il existe au moins un chemin entre deux maisons quelconques en utilisant un sous-ensemble des routes données.

Entrée

La première ligne contient les entiers naturels $N$ ($1 \le N \le 100\,000$), $M$ ($1 \le M \le 300\,000$) et $K$ ($1 \le K \le 17$), qui représentent le nombre d'habitants, le nombre de routes et le nombre d'abris antiatomiques. Les maisons sont numérotées de $1$ à $N$.

Dans chacune des $M$ lignes suivantes, il y a trois entiers naturels $A$, $B$ ($1 \le A, B \le N, A \neq B$) et $C$ ($1 \le C \le 10^9$) indiquant qu'il existe une route entre les maisons $A$ et $B$ dont le parcours nécessite $C$ unités de temps.

Dans chacune des $K$ lignes suivantes, il y a deux entiers naturels $X$ ($1 \le X \le N$) et $Y$ ($1 \le Y \le 10^9$) indiquant qu'il y a un abri antiatomique dans la maison $X$ pouvant accueillir au plus $Y$ personnes. La capacité totale de tous les abris sera supérieure ou égale à $N$.

Sortie

Sur une seule ligne, affichez le temps minimal nécessaire pour évacuer tous les habitants de cette ville.

Bodovanje

Exemples

Entrée 1

5 5 2 
1 2 1 
1 3 3 
2 3 4 
3 4 1 
4 5 1 
1 10 
4 2

Sortie 1

3

Remarque

En 3 unités de temps, les personnes des maisons 1, 2 et 3 peuvent se rendre à l'abri de la maison 1, et les personnes des maisons 4 et 5 à l'abri de la maison 4. En moins de temps, toutes les personnes ne peuvent pas atteindre les abris car l'abri de la maison 4 ne peut accueillir que deux personnes au maximum.

Entrée 2

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

Sortie 2

5