我们不妨思考一下，两个串的(LCP)的长度在(Trie)树上是什么？
对应点的(LCA)的深度。
然后就可以想到把边看成点，然后把边与边之间连边，点权看成这条边经过所需要的时间。
但是这样子连边是(O(m^2))的，不够优秀。
我们需要进一步优化。
考虑两个点之间的(LCP)可以用什么来代替？
(SA)里面的(height)对吧。
所以此时我们就是(min_{i=l}^rh_i)。
此时就不难想到用前后缀优化连边了。
/*
mail: mleautomaton@foxmail.com
author: MLEAutoMaton
This Code is made by MLEAutoMaton
*/
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<iostream>
using namespace std;
#define ll long long
#define re register
#define file(a) freopen(a".in","r",stdin);freopen(a".out","w",stdout)
inline int gi(){
int f=1,sum=0;char ch=getchar();
while(ch>'9' || ch<'0'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0' && ch<='9'){sum=(sum<<3)+(sum<<1)+ch-'0';ch=getchar();}
return f*sum;
}
const int N=1000010;
int front[N],cnt,dfn[N],f[N][20],dep[N],n,m,k,d[N],val[N],pl[N],sl[N],pr[N],sr[N];
struct node{int to,nxt,w;}e[N<<1];
vector<int>in[N],out[N];
int dis[N],vis[N],Time,que[N],all;
void Add(int u,int v,int w){e[++cnt]=(node){v,front[u],w};front[u]=cnt;}
typedef pair<int,int> pii;
priority_queue<pii,vector<pii>,greater<pii> >q;
#define mp make_pair
void dfs(int u){
dfn[u]=++Time;
for(int i=1;i<=18;i++)f[u][i]=f[f[u][i-1]][i-1];
for(int i=front[u];i;i=e[i].nxt){
int v=e[i].to;f[v][0]=u;dep[v]=dep[u]+1;
dfs(v);
}
}
int lca(int x,int y){
if(dep[x]<dep[y])swap(x,y);
for(int i=18;~i;i--)
if(dep[x]-(1<<i)>=dep[y])x=f[x][i];
if(x==y)return x;
for(int i=18;~i;i--)
if(f[x][i]!=f[y][i])x=f[x][i],y=f[y][i];
return f[x][0];
}
bool cmp(int a,int b){return dfn[d[abs(a)]]<dfn[d[abs(b)]];}
void build(int x){
int num=0;
for(int i:in[x])que[++num]=i;
for(int i:out[x])que[++num]=-i;
sort(que+1,que+num+1,cmp);
for(int i=1;i<=num;i++){
pl[i]=++all;pr[i]=++all;
sl[i]=++all;sr[i]=++all;
if(i>1){
Add(pl[i-1],pl[i],0);Add(pr[i-1],pr[i],0);
Add(sl[i],sl[i-1],0);Add(sr[i],sr[i-1],0);
}
if(que[i]>0){Add(que[i],pl[i],0);Add(que[i],sl[i],0);}
else{que[i]=-que[i];Add(pr[i],que[i],0);Add(sr[i],que[i],0);}
}
for(int i=1;i<num;i++){
int w=dep[lca(d[que[i]],d[que[i+1]])];
Add(pl[i],pr[i+1],w);Add(sl[i+1],sr[i],w);
}
}
void dijkstra(){
int tot=0;
while(!q.empty()){
pii now=q.top();q.pop();int u=now.second;
if(vis[u])continue;vis[u]=1;tot++;
if(tot==all)break;
for(int i=front[u];i;i=e[i].nxt){
int v=e[i].to;
if(!vis[v] && dis[v]>dis[u]+e[i].w+val[v]){
dis[v]=dis[u]+e[i].w+val[v];
q.push(mp(dis[v],v));
}
}
}
while(!q.empty())q.pop();
}
void solve(){
memset(front,0,sizeof(front));cnt=0;
memset(vis,0,sizeof(vis));memset(dis,127,sizeof(dis));
memset(val,0,sizeof(val));memset(d,0,sizeof(d));
memset(dep,0,sizeof(dep));memset(dfn,0,sizeof(dfn));
n=gi();m=gi();k=gi();all=m;Time=0;
for(int i=1;i<=n;i++)in[i].clear(),out[i].clear();
for(int i=1;i<=m;i++){
int u=gi(),v=gi();val[i]=gi();d[i]=gi();
if(u==1)q.push(mp(dis[i]=val[i],i));
out[u].push_back(i);in[v].push_back(i);
}
for(int i=1;i<k;i++){int x=gi(),y=gi();gi();Add(x,y,0);}
dfs(1);
memset(front,0,sizeof(front));cnt=0;
for(int i=1;i<=n;i++)build(i);
dijkstra();
for(int i=2;i<=n;i++){
int ans=dis[0];
for(int j:in[i])ans=min(ans,dis[j]);
printf("%d
",ans);
}
}
int main(){
#ifndef ONLINE_JUDGE
freopen("in.in","r",stdin);
#endif
int T=gi();
while(T--)solve();
return 0;
}