/*
根据claris的 博客以及 beginend 的博客来写的 首先考虑如何求出最短路 可以从样例看出 路径是从边走到边的， 所以我们将边看作点 有共同端点的两边之间
互相连边， 边权为lcp。 这条边自己的花费计算要拆点， 拆成的两个点之间连原来的花费 这样跑最短路就可以啦 然而这样的做法有问题， 考虑边数最大可能是M^2切要求M^2个lca 显然不行 这里采用claris巨佬的方法 /*********beginend的题解*******
假如现在有n个节点a[1..n]要两两求lca，我们将其按dfs序排序，设h[i]=dep[lca(a[i],a[i+1])]，根据后缀数组height数组的性质不难得到dep[lca(a[i],a[j])]=min(h[i]..h[j-1])。
那么我们可以枚举中间的每个h[i]，i两边的点就可以至少花费h[i]的费用来互相访问。我们只要建立前缀虚点和后缀虚电来优化连边即刻。 */
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
#include<iostream>
#define M 100200
#define ll long long
#define id1(x) x * 2 - 1
#define id2(x) x * 2
using namespace std;
int n,m, k, deep[M], dfn[M], size[M], fa[M], son[M], top[M], ls[M], inh[M], outh[M], inx[M], outx[M], pst[M];
int inp[M], outp[M], ins[M], outs[M], sz, head[M * ], cnt, tm, to[M << ], nxt[M << ], ver[M << ], a[M];
ll dis[M * ];
bool vis[M * ], in[M], out[M];
int read() {
int nm = , f = ;
char c = getchar();
for(; !isdigit(c); c = getchar()) if(c == '-') f = -;
for(; isdigit(c); c = getchar()) nm = nm * + c -'';
return nm * f;
} void init() {
cnt = tm = ;
memset(head, , sizeof(head));
memset(ls, , sizeof(ls));
memset(inh, , sizeof(inh));
memset(outh, , sizeof(outh));
memset(son, , sizeof(son));
} void push(int vi, int vj, int wei) {
cnt++, to[cnt] = vj, ver[cnt] = wei, nxt[cnt] = head[vi], head[vi] = cnt;
if(cnt >= (M << )) {
puts("gg");
exit();
}
} void add(int vi, int vj) {
cnt++, to[cnt] = vj, nxt[cnt] = ls[vi], ls[vi] = cnt;
} void dfs1(int now) {
size[now] = ;
int maxx = ;
for(int i = ls[now]; i; i = nxt[i]) {
int vj = to[i];
deep[vj] = deep[now] + ;
fa[vj] = now;
dfs1(vj);
size[now] += size[vj];
if(size[vj] > maxx) maxx = size[vj], son[now] = vj;
}
} void dfs2(int now) {
dfn[now] = ++tm;
if(son[now]) {
top[son[now]] = top[now];
dfs2(son[now]);
}
for(int i = ls[now]; i; i = nxt[i]) {
int vj = to[i];
if(vj == son[now]) continue;
top[vj] = vj;
dfs2(vj);
}
} void spfa() {
for(int i = ; i <= sz; i++) dis[i] = 10000000000000000ll;
queue<int>q;
q.push();
dis[] = ;
vis[] = true;
while(!q.empty()) {
int op = q.front();
q.pop();
vis[op] = false;
for(int i = head[op]; i; i = nxt[i]) {
int vj = to[i];
if(dis[vj] > dis[op] + ver[i]) {
dis[vj] = dis[op] + ver[i];
if(!vis[vj]) {
vis[vj] = true;
q.push(vj);
}
}
}
}
} void dijk() {
for(int i = ; i <= sz; i++) dis[i] = 10000000000000000ll, vis[i] = ;
dis[] = ;
priority_queue<pair<int,int> > q;
q.push(make_pair(,));
while(!q.empty()) {
pair<int, int> now = q.top();
q.pop();
while(!q.empty() && vis[now.second]) now = q.top(), q.pop();
if(vis[now.second]) break;
int op = now.second;
vis[op] = true;
for(int i = head[op]; i; i = nxt[i]) {
int vj = to[i];
if(dis[vj] > dis[op] + ver[i]) {
dis[vj] = dis[op] + ver[i];
q.push(make_pair(-dis[vj],vj));
}
}
}
} int lca(int x, int y) {
while(top[x] != top[y]) {
if(deep[top[x]] < deep[top[y]]) swap(x, y);
x = fa[top[x]];
}
return deep[x] < deep[y] ? x : y;
} bool cmp(int x, int y) {
return dfn[pst[x]] < dfn[pst[y]];
} int main() {
int T = read();
while(T--) {
init();
n = read(), m = read(), k = read();
sz = m * ;
for(int i = ; i <= m; i++) {
int vi = read(), vj = read(), wei = read();
pst[i] = read();
push(id1(i), id2(i), wei);
inx[i] = inh[vj], inh[vj] = i, outx[i] = outh[vi], outh[vi] = i;
}
for(int i = ; i < k; i++) {
int vi = read(), vj = read();
read();
add(vi, vj);
}
dfs1(), top[] = fa[] = ;
dfs2();
for(int x = ; x <= n; x++) {
int a1 = ;
for(int i = inh[x]; i; i = inx[i]) a[++a1] = i, in[i] = ;
for(int i = outh[x]; i; i = outx[i]) a[++a1] = i, out[i] = ;
sort(a + , a + a1 + , cmp);
for(int i = ; i <= a1; i++) {
inp[i] = ++sz;
outp[i] = ++sz;
if(in[a[i]]) push(id2(a[i]), inp[i], );
if(out[a[i]]) push(outp[i], id1(a[i]), );
if(i > ) push(inp[i - ], inp[i], ), push(outp[i - ], outp[i], );
}
for(int i = a1; i >= ; i--) {
ins[i] = ++sz;
outs[i] = ++sz;
if(in[a[i]]) push(id2(a[i]), ins[i], );
if(out[a[i]]) push(outs[i], id1(a[i]), );
if(i < a1) push(ins[i + ], ins[i], ), push(outs[i + ], outs[i], );
}
for(int i = ; i < a1; i++) {
int lc = deep[lca(pst[a[i]], pst[a[i + ]])];
push(inp[i], outp[i + ], lc);
push(ins[i + ], outs[i], lc);
}
for(int i = ; i <= a1; i++) in[a[i]] = out[a[i]] = ;
}
for(int i = outh[]; i; i = outx[i]) push(, id1(i), );
//spfa();
dijk();
for(int x = ; x <= n; x++) {
ll mn = 10000000000000000ll;
for(int i = inh[x]; i; i = inx[i]) mn = min(mn, dis[id2(i)]);
cout << mn << "\n";
}
}
return ;
} /*
2
4 4 6
1 2 2 5
2 3 2 5
2 4 1 6
4 2 1 6
1 2 1
2 3 1
3 4 1
4 5 2
1 6 2 4 4 6
1 2 2 5
2 3 2 5
2 4 1 6
4 2 1 6
1 2 1
2 3 1
3 4 1
4 5 2
1 6 2 */