In the first line of the standard input, there are three integers, N,M and K (2<=N<=5000,1<=M<=5000,1<=K<=1000000) These denote, respectively: the number of ports in the waters frequented by the sailors who told Bytensson their stories, the number of waterways, and the number of tales.
The M lines that follow specify the waterways. A single waterway's description consists of a single line that contains two integers, a and b (1<=a,b<=N,a<>b) separated by a single space; these specify the numbers of ports at the two ends of this particular waterway.
The K lines that follow specify the tales that Bytensson has heard. A single tale's description consists of a single line with three integers, s,t and d (1<=S,T<=N,1<=d<=1000000000) separated by single spaces. These indicate that the tale's protagonist set sail from port no. s, ended the journey in port no. t, and sailed exactly d times through various waterways.