Laiko ribojimas: 1s

Atminties ribojimas: 1024MB

Duomenų failas: susisiekimo_pertvarka.in

Rezultatų failas: susisiekimo_pertvarka.out

Jei norite pateikti savo sprendimą - prisijunkite.

5. Domantas ir susisiekimo pertvarka

Domantas yra šalies A prezidentas. Šalyje yra n miestų sunumeruotų nuo 1 iki n. Miestas '1' yra šalies sostinė. Šalyje yra m kelių jungiančių miestus. kelias i jungia miestus u_i,v_i atstumu x_i. Taipogi šalyje yra k traukinių maršrutų. Kiekvienas traukinio maršrutas jungia sostinę su miestu s_i atstumu y_i.

Domantas nenori švaistyti šalies pinigų, todėl nutarė uždaryti kai kuriuos traukinių maršrutus. Jūsų užduotis - surasti, kiek maksimaliai traukinių maršrutų Domantas gali pašalinti laikydamasis vienos sąlygos: pašalinus maršrutus trumpiausi kelio ilgiai nuo kiekvieno miesto iki sostinės turi nesikeisti.

Pradiniai duomenys

Pirmoje eilutėje pateikti trys sveikieji skaičiai n, m, k (2\\leqn\\leq10^5,1\\leqm\\leq3*10^5,1\\leqk\\leq10^5).

Sekančiose m eilučių pateikta po tris skaičius u_i,v_i,x_i - kelias tarp miestų u_i,v_i su atstumu x_i.

Sekančiose k eilučių pateikta po du skaičius s_i,y_i - maršrutas tarp sostinės ir miesto s_i atstumu y_i.

Rezultatai

Išveskite vieną skaičių - maksimalų kiekį, kiek galima pašalinti traukinių maršrutų.

Pavyzdžiai

Pradiniai duomenys Rezultatai 
5 5 3
1 2 1
2 3 2
1 3 3
3 4 4
1 5 5
3 5
4 5
5 5
 
2