###题目描述

给定一个无向图，初始有 $n$ 个节点和 $m$ 条边，边上有权值 $w$。

添加 $Q$ 条新边(连接原始节点与两个特殊节点 $S = n+1$ 和 $T = n+2$，边权为 $w$)。

对于初始的 $m$ 条边， 判断该边是否在 $S$ 到 $T$ 的某条最短路径上。

如果是，输出该最短路的权值之和 $w$;

否则 输出“GG”。

输入格式

第一行:整数 $n$(原始节点数量)。

第二行:两个整数 $m$ 和 $Q$(初始边数和新边数)。

接下来 $m$ 行:每行三个整数 $u, v, w$，表示第 $i$ 条初始边。

接下来 $Q$ 行:每行三个整数 $u,v,w$，表示新边($u$ 或 $v$ 是 $n+1$ 或 $n+2$)。

输出格式

输出 $m$ 行，第 $i$ 行表示第 $i$ 条初始边的结果。

如果经过这条边不能同时到达 $S$ 和 $T$，那么输出一行“GG”(不包含引号) 否则输出一个数，表示经过这条边的 $S$ 到 $T$ 之间的最短路。

样例 1 输入

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

样例 1 输出

12 
11 
15

数据范围

• 对于$30\%$的数据，$n≤5,m,Q≤5$。

• 对于$50\%$的数据，$n≤50,m,Q≤5$。

• 对于$70\%$的数据，$n≤50,m,Q≤1000$。

• 对于$100\%$的数据，$n,m,Q≤10^4,0<w≤100$。