#include<bits/stdc++.h>
#define poly vector<int>
#define IOS ios::sync_with_stdio(false)
#define ll long long
#define mp make_pair
#define mt make_tuple
#define pa pair < int,int >
#define fi first
#define se second
#define inf 1e18
#define mod 998244353
#define sz(x) ((int)((x).size()))
#define int ll
// #define N 
using namespace std;
const int N=1000005;
struct node
{
	int x,y,w,d;
}E[N];
namespace tr
{
	int dfn[N],DFN;
	int ffa[N],siz[N],dep[N];
	int son[N];
	poly G[N];
	int Tp[N];
	void dfs(int k,int fa)
	{
		dfn[k]=++DFN;
		ffa[k]=fa;
		siz[k]=1;
		son[k]=0;
		dep[k]=dep[fa]+1;
		for (auto u:G[k])
		{
			dfs(u,k);
			siz[k]+=siz[u];
			if (siz[u]>siz[son[k]]) son[k]=u;
		}
	}
	void dfs1(int k,int tp)
	{
		Tp[k]=tp;
		if (son[k]) dfs1(son[k],tp);
		for (auto u:G[k])
		{
			if (u==son[k]) continue;
			dfs1(u,u);
		}
	}
	inline int lca(int x,int y)
	{
		while (Tp[x]!=Tp[y])
		{
			if (dep[Tp[x]]<dep[Tp[y]]) swap(x,y);
			x=ffa[Tp[x]];
		}
		if (dep[x]<dep[y]) return x;
		return y;
	}
}
vector<pa>G[N];
poly rG[N],Q[N];
int id[N][3];
int dis[N],ans[N];
int tot;
int n,m,q;
inline void add(int x,int y,int w)
{
	G[x].push_back(mp(y,w));
}
void dfs(int k,int fa)
{
	int x=0;
	for (auto u:rG[k])
	{
		// cout <<"rG "<<u<<" "<<k<<endl;
		dfs(u,k);
		add(id[u][0],id[k][0],0);
		add(id[k][1],id[u][1],0);
	}
	for (auto u:rG[k])
	{
		if (x) add(id[u][0],x,tr::dep[k]-1);
		++tot;
		if (x) add(tot,x,0);
		add(tot,id[u][1],0);
		x=tot;
	}
	reverse(rG[k].begin(),rG[k].end());
	x=0;
	for (auto u:rG[k])
	{
		if (x) add(id[u][0],x,tr::dep[k]-1);
		++tot;
		if (x) add(tot,x,0);
		add(tot,id[u][1],0);
		x=tot;
	}
	add(id[k][1],id[k][2],0);
	add(id[k][0],id[k][2],tr::dep[k]-1);
}
void BellaKira()
{
	cin>>n>>m>>q;
	tot=m;
	for (int i=1;i<=m;i++)
	{
		cin>>E[i].x>>E[i].y>>E[i].w>>E[i].d;
		Q[E[i].y].push_back(i);
		Q[E[i].x].push_back(i);
	}
	for (int i=1;i<q;i++)
	{
		int x,y,w;
		cin>>x>>y>>w;
		tr::G[x].push_back(y);
	}
	tr::dfs(1,0);
	tr::dfs1(1,0);
	for (int i=1;i<=n;i++)
	{
		sort(Q[i].begin(),Q[i].end(),[&](int x,int y)
		{
			return tr::dfn[E[x].d]<tr::dfn[E[y].d];
		});
		poly sta,all;
		sta.push_back(1);
		all.push_back(1);
		for (auto v:Q[i])
		{
			int u=E[v].d;
			if (u==sta.back()) continue;
			if (sta.size()==1) 
			{
				sta.push_back(u);
				all.push_back(u);
				continue;
			}
			int x=tr::lca(sta.back(),u);
			while (sta.size()>=2&&tr::dfn[sta[sz(sta)-2]]>=tr::dfn[x]) rG[sta[sz(sta)-2]].push_back(sta.back()),sta.pop_back();
			if (x!=sta.back()) 
			{
				rG[x].push_back(sta.back());
				sta.pop_back();

				sta.push_back(x);
				all.push_back(x);
			}
			sta.push_back(u);
			all.push_back(u);
		}
		while (sta.size()>1) rG[sta[sz(sta)-2]].push_back(sta.back()),sta.pop_back();
		for (auto u:all) id[u][0]=++tot,id[u][1]=++tot,id[u][2]=++tot;
		dfs(1,0);
		for (auto u:all) poly().swap(rG[u]);
		for (auto u:Q[i])
		{
			if (E[u].y==i) add(u,id[E[u].d][0],0),add(u,id[E[u].d][1],tr::dep[E[u].d]-1);
			if (E[u].x==i) add(id[E[u].d][2],u,E[u].w);
		}
	}
	priority_queue<pa>q;
	for (int i=1;i<=tot;i++) dis[i]=inf;
	for (int i=1;i<=m;i++)
		if (E[i].x==1)
		{
			dis[i]=E[i].w;
			q.push(mp(-dis[i],i));
		}
	while (!q.empty())
	{
		int ww=-q.top().fi;
		int u=q.top().se;
		q.pop();
		if (ww!=dis[u]) continue;
		for (auto [v,w]:G[u])
			if (dis[v]>dis[u]+w)
			{
				dis[v]=dis[u]+w;
				q.push(mp(-dis[v],v));
			}
	}
	for (int i=1;i<=n;i++) ans[i]=inf;
	ans[1]=0;
	for (int i=1;i<=m;i++)
		ans[E[i].y]=min(ans[E[i].y],dis[i]);
	for (int i=2;i<=n;i++) cout<<ans[i]<<'\n';

	for (int i=1;i<=tot;i++) vector<pa>().swap(G[i]);
	for (int i=1;i<=n;i++)
	{
		poly().swap(Q[i]);
	}
	for (int i=1;i<=::q;i++)
		poly().swap(tr::G[i]);
	tr::DFN=0;
}
signed main()
{
	IOS;
	cin.tie(0);
	int T=1;
	cin>>T;
	while (T--)
	{
		BellaKira();
	}
}
/*list:
1.mod 998244353 or 1e9+7 or ???
2.N
3.duipai shuju xingtai duoyidian
...
*/