1812: xls的破产故事

ybs一直说xls有钱，其实xls真的没钱。这不寒假临近，xls决定拿出所剩不多的钱出去旅游，计划去n个城市，每个城市xls只决定去一次，n个城市中存在m条路径，每条路径连接两个城市，当然每条路径有属于它的过路费，问xls最少需要准备多少肾（钱）才能出去旅游？
但是这n个城市处于火山活跃地震频发的地方，所以指不定就会有道路损坏无法通过，需要更换路径的情况，所以有q次询问，每次给出u,v,w三个整数，代表路径（u，v）的过路费改为w，问在道路损害的情况下xls需要准备的最小rmb。每次询问独立。

第一行给出三个整数n,m,q（2<=n<=1000,1<=m<=((n-1)*n/2)，1<=q<=100000),分别表示城市数，路径数，询问次数。
下面接m行，每行给出三个整数u,v,w（0<=u,v<n,(u!=v)，1<=w<=100000）,u,v代表城市编号，w代表路径的过路费。
下面接q行，每行三个整数u,v，w（0<=u,v<n,(u!=v)，1<=w<=100000）,表示路径（u,v）的过路费改为w。

q行，每行一个整数表示答案。

3 3 3
0 1 3
0 2 2
1 2 5
0 2 3
1 2 6
0 1 6

6
5
7