#include<bits/stdc++.h>
#define ll long long
#define get_lg(x) (31-__builtin_clz(x))
#define in(x) ((x)*6-5)
#define out(x) ((x)*6-4)
#define inp(x) ((x)*6-3)
#define ins(x) ((x)*6-2)
#define outp(x) ((x)*6-1)
#define outs(x) ((x)*6)
#define pii pair<int,int>
#define fi first
#define se second

using namespace std;
const int N=5e4,M=5e4,K=2e4,inf=2e9;
struct edge{
	int v,w,kid,id;
};
struct edge1{
	int v,w;
};
int T;
int n,m,k;
vector<edge>g[N+10],reg[N+10];
vector<int>trie[K+10];
vector<edge1>g1[M*6+10];
int dfs_num;
int dep[K+10],dfn[K+10],red[K+10];
int pw[17];
int e_idx;
int e[17][K*2+10],el[K+10],er[K+10];
int p_idx;
pii p[M+10];
int po[M+10],pi[M+10],so[M+10],si[M+10];
int dis[M*6+10],vis[M*6+10];
priority_queue<pii,vector<pii >,greater<pii > >q;
inline int query(int l,int r){
	int lg=get_lg(r-l+1);
	return min(e[lg][l],e[lg][r-pw[lg]+1]);
}
inline int lca(int x,int y){
	return red[query(min(el[x],el[y]),max(er[x],er[y]))];
}
inline void dfs(int u){
	dfn[u]=++dfs_num;
	red[dfs_num]=u;
	++e_idx;
	e[0][e_idx]=dfn[u];
	el[u]=e_idx;
	for(auto v:trie[u]){
		dep[v]=dep[u]+1;
		dfs(v);
		++e_idx;
		e[0][e_idx]=dfn[u];
	}
	er[u]=e_idx;
}
inline void dijkstra(){
	for(int i=0;i<=m*6;++i){
		dis[i]=inf;
		vis[i]=0;
	}
	dis[0]=0;
	q.push({0,0});
	while(!q.empty()){
		pii u=q.top();
		q.pop();
		if(!vis[u.se]){
			vis[u.se]=1;
			for(auto eg:g1[u.se]){
				int v=eg.v,w=eg.w;
				if(dis[v]>dis[u.se]+w){
					dis[v]=dis[u.se]+w;
					q.push({dis[v],v});
				}
			}
		}
	}
}
int main(){
//	freopen("test.in","r",stdin);
//	freopen("test.out","w",stdout);
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	cin>>T;
	while(T--){
		cin>>n>>m>>k;
		for(int i=1;i<=n;++i){
			g[i].clear();
			reg[i].clear();
		}
		for(int i=1;i<=k;++i){
			trie[i].clear();
		}
		for(int i=0;i<=m*6;++i){
			g1[i].clear();
		}
		for(int i=1;i<=m;++i){
			int u,v,w,id;
			cin>>u>>v>>w>>id;
//			if(u==v){
//				--i;
//				--m;
//				continue;
//			}
			g[u].push_back({v,w,id,i});
			reg[v].push_back({u,w,id,i});
			g1[in(i)].push_back({out(i),w});
			g1[inp(i)].push_back({in(i),0});
			g1[ins(i)].push_back({in(i),0});
			g1[out(i)].push_back({outp(i),0});
			g1[out(i)].push_back({outs(i),0});
		}
		for(int i=1;i<k;++i){
			int u,v,w;
			cin>>u>>v>>w;
			trie[u].push_back(v);
		}
		dfs_num=0;
		e_idx=0;
		dfs(1);
		pw[0]=1;
		for(int i=1;i<=16;++i){
			pw[i]=pw[i-1]<<1;
		}
		for(int tp=1;pw[tp]<=e_idx;++tp){
			for(int i=1;i+pw[tp]-1<=e_idx;++i){
				e[tp][i]=min(e[tp-1][i],e[tp-1][i+pw[tp-1]]);
			}
		}
		for(int i=2;i<=n;++i){
			p_idx=0;
			for(auto eg:reg[i]){
				p[++p_idx]={dfn[eg.kid],eg.id};
			}
			for(auto eg:g[i]){
				p[++p_idx]={dfn[eg.kid],-eg.id};
			}
			sort(p+1,p+p_idx+1);
			for(int j=1;j<=p_idx;++j){
				po[j]=po[j-1];
				pi[j]=pi[j-1];
				if(p[j].se>0){
					if(po[j]){
						g1[outp(p[po[j]].se)].push_back({outp(p[j].se),0});
					}
					po[j]=j;
				}
				else{
					if(pi[j]){
						g1[inp(-p[pi[j]].se)].push_back({inp(-p[j].se),0});
					}
					pi[j]=j;
				}
			}
			so[p_idx+1]=0;
			si[p_idx+1]=0;
			for(int j=p_idx;j;--j){
				so[j]=so[j+1];
				si[j]=si[j+1];
				if(p[j].se>0){
					if(so[j]){
						g1[outs(p[so[j]].se)].push_back({outs(p[j].se),0});
					}
					so[j]=j;
				}
				else{
					p[j].se=-p[j].se;
					if(si[j]){
						g1[ins(p[si[j]].se)].push_back({ins(p[j].se),0});
					}
					si[j]=j;
				}
			}
			for(int j=1;j<p_idx;++j){
				p[j].fi=dep[lca(red[p[j].fi],red[p[j+1].fi])];
				if(po[j]&&si[j+1]){
					g1[outp(p[po[j]].se)].push_back({inp(p[si[j+1]].se),p[j].fi});
				}
				if(so[j+1]&&pi[j]){
					g1[outs(p[so[j+1]].se)].push_back({ins(p[pi[j]].se),p[j].fi});
				}
			}
		}
		for(auto eg:g[1]){
			g1[0].push_back({in(eg.id),0});
		}
		dijkstra();
		for(int i=2;i<=n;++i){
			int ans=inf;
			for(auto eg:reg[i]){
				ans=min(ans,dis[out(eg.id)]);
			}
			cout<<ans<<'\n';
		}
	}
	return 0;
}