C国的交通系统由n座城市与m条连接两座城市的双向道路构成,第i(1<i<m) 条道路连接城市 ui;和 vi。任意两座城市都能通过若干条道路相互到达。 然而,近期由于一场大地震,所有m条道路都被破坏了,修复第i(1≤i<m)条道路的费用为wi;。与此同时,C国还有k个准备进行城市化改造的乡镇。对于第j(1<j≤k)个乡镇，C国对其进行城市化改造的费用为c。在城市化改造完第j(1≤j≤k)个乡镇后，可以在这个乡镇与原来的n座城市间建造若干条道路，其中在它与第i(1≤i≤n)座城市间建造一条道路的费用为aj,i。C国可以在这k个乡镇中选择任意多个进行城市化改造，也可以不选择任何乡镇进行城市化改造。 为尽快恢复城市间的交通，C国政府希望以最低的费用将原有的座城市两两连通，也即任意两座原有的城市都能通过若干条修复或新建造的道路相互到达。你需要帮助他们求出，将原有的n座城市两两连通的最小费用。
输入的第一行包含三个非负整数n,m,k，分别表示原有的城市数量、道路数量和准备进行城市化改造的乡镇数量。 输入的第i+1(1≤i≤m)行包含三个非负整数ui,vi,wi，表示第i条道路连接的两座城市与修复该道路的费用。 输入的第 j+m+1(1≤j≤k)行包含 n+1个非负整数 cj,aj,1,1,aj,2j,...,aj,n，分别表示将第j个乡镇进行城市化改造的费用与在该乡镇与原有的城市间建造道路的费用。
输出一行一个非负整数，表示将原有的n座城市两两连通的最小费用，
4 4 2 1 4 6 2 3 7 4 2 5 4 3 4 1 1 8 2 4 100 1 3 2 4
13
C国政府可以选择修复第3条和第4条道路，然后将第1个乡镇进行城市化改造并建造它与第1,3座城市间的道路，总费用为5+4+1+1+2=13。可以证明，不存在比13更小的费用能使原有的4座城市两两连通。
【数据范围】 对于所有测试数据，保证：
==
| 测试点编号 | n≤ | m≤ | k≤ | 特殊性质 |
|---|---|---|---|---|
| 1∼4 | 104 | 106 | 0 | 无 |
| 5,6 | 103 | 105 | 5 | A |
| 7,8 | ^ | ^ | ^ | 无 |
| 9,10 | ^ | 106 | ^ | A |
| 11,12 | ^ | ^ | ^ | 无 |
| 13,14 | ^ | ^ | 10 | A |
| 15,16 | ^ | ^ | ^ | 无 |
| 17,18 | 104 | ^ | 5 | A |
| 19,20 | ^ | ^ | ^ | 无 |
| 21∼25 | ^ | ^ | 10 | ^ |
特殊性质 A：对于所有 1≤j≤k，均有 cj=0 且均存在 1≤i≤n 满足 aj,i=0。
