Description：

给出一个带权有向图，每条边有一个口令，他们都在一棵 $trie$ 树上，必须口令匹配才能经过，每次可以在某个节点花费 $LCP$ 的代价换口令，求从 $1$ 到其他所有点的最短路。

$1\leqslant n\leqslant 50000$

##Solution：

那个 $LCP$ 的代价不太容易在最短路里体现，因此我们考虑把边拆成两个点，一个入点一个出点，之间连原来的边权，然后对于每个点，把所有进这个点的边的出点向所有离开这个点的边的入点连边，边权为 $LCP$ ，然而这样建边边的个数还是 $O(m^2)$ 的，我们可以把每条出边和入边分别按在 $trie$ 树上的 $dfs$ 序排序，然后两两之间求出 $height$ 数组，那么两个字符串 $i,j$ 的 $lcp$ 就是区间 $\min height$ ，那么对于一个 $i$ ，我们一定可以用不超过 $h[i]$ 的代价从 $i$ 一侧的入点走到另一侧的出点，那么我们就可以使用一个叫做前后缀优化建图的技巧，也就是把图建成这样：

上面是入点，下面是出点，就可以实现一个前缀向一个后缀连边。

但是这样只能单向连，于是我们把一条边拆成两个入点两个出点，分别向前向后连，然后这四个点连成这样：

就行了。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<queue>

#include<cctype>

#include<cstring>

using namespace std;

inline int rd()

{

	register int res = 0,f = 1;register char c = getchar();

	while(!isdigit(c)){if(c == '-')f = -1;c = getchar();}

	while(isdigit(c))res = (res << 1) + (res << 3) + c - '0',c = getchar();

	return res * f;

}

int n,m,p;

#define MAXN 50010

namespace DIJ

{

	#define MAXE (MAXN * 30)

	#define MAXP (MAXN * 5)

	struct edge

	{

		int to,nxt,v;

	}e[MAXE];

	int edgenum = 0;

	int lin[MAXP] = {0};

	void add(int a,int b,int c)

	{//cout << a << " -> " << b << " : " << c << endl;

		e[++edgenum] = (edge){b,lin[a],c};lin[a] = edgenum;

		return;

	}

	long long d[MAXP];

	bool vis[MAXP];

	int s;

	void dijkstra()

	{

		memset(vis,false,sizeof(vis));

		memset(d,0x3f,sizeof(d));d[s] = 0;

		priority_queue< pair<long long,int> > q;q.push(make_pair(0,s));

		while(!q.empty())

		{

			int k = q.top().second;q.pop();

			if(vis[k])continue;

			vis[k] = true;

			for(int i = lin[k];i != 0;i = e[i].nxt)

			{

				if(d[e[i].to] > d[k] + e[i].v)

				{

					d[e[i].to] = d[k] + e[i].v;

					q.push(make_pair(-d[e[i].to],e[i].to));

				}

			}

		}

		return;

	}

	void init()

	{

		edgenum = 0;

		memset(lin,0,sizeof(lin));

		return;

	}

}

namespace TRIE

{

	struct edge

	{

		int to,nxt;

	}e[MAXN];

	int edgenum = 0;

	int lin[MAXN] = {0};

	void add(int a,int b)

	{

		e[++edgenum] = (edge){b,lin[a]};lin[a] = edgenum;

		return;

	}

	int fa[MAXN],top[MAXN],dep[MAXN],son[MAXN],siz[MAXN];

	int dfn[MAXN],tot = 0;

	void dfs1(int k,int depth)

	{

		dep[k] = depth;

		siz[k] = 1;

		for(int i = lin[k];i != 0;i = e[i].nxt)

		{

			if(e[i].to != fa[k])

			{

				fa[e[i].to] = k;

				dfs1(e[i].to,depth + 1);

				siz[k] += siz[e[i].to];

				if(son[k] == 0 || siz[e[i].to] > siz[son[k]])son[k] = e[i].to;

			}

		}

		return;

	}

	void dfs2(int k,int tp)

	{

		top[k] = tp;

		dfn[k] = ++tot;

		if(son[k] == 0)return;

		dfs2(son[k],tp);

		for(int i = lin[k];i != 0;i = e[i].nxt)

		{

			if(e[i].to != fa[k] && e[i].to != son[k])

			{

				dfs2(e[i].to,e[i].to);

			}

		}

		return;

	}

	int LCA(int a,int b)

	{

		while(top[a] != top[b])

		{

			if(dep[top[a]] < dep[top[b]])swap(a,b);

			a = fa[top[a]];

		}

		return (dep[a] < dep[b] ? a : b);

	}

	int LCP(int a,int b){return dep[LCA(a,b)] - 1;}

	void init()

	{

		edgenum = tot = 0;

		memset(lin,0,sizeof(lin));

		memset(son,0,sizeof(son));

		memset(e,0,sizeof(e));

		return;

	}

}

int pcnt = 0;

namespace GRAPH

{

	struct edge

	{

		int to,nxt,v,d,ty,id;

	}e[MAXN << 1];

	int edgenum = 0;

	int lin[MAXN] = {0};

	void add(int a,int b,int l,int d,int id)

	{

		e[++edgenum] = (edge){b,lin[a],l,d,1,id};lin[a] = edgenum;

		e[++edgenum] = (edge){a,lin[b],l,d,0,id};lin[b] = edgenum;

		return;

	}

	void init()

	{

		edgenum = 0;

		memset(lin,0,sizeof(lin));

		memset(e,0,sizeof(e));

		return;

	}

}

int id[MAXN][5],idp[MAXN];

int s[MAXN],tp = 0;

int s1[MAXN],tp1 = 0;

int s2[MAXN],tp2 = 0;

bool cmp_es_dfn(int a,int b){return TRIE::dfn[GRAPH::e[a].d] < TRIE::dfn[GRAPH::e[b].d];}

void work()

{

	DIJ::init();TRIE::init();GRAPH::init();

	pcnt = 0;

	scanf("%d%d%d",&n,&m,&p);

	int a,b,c,d;

	for(int i = 1;i <= m;++i)

	{//cout << "###" << endl;

		a = rd();b = rd();c = rd();d = rd();

		GRAPH::add(a,b,c,d,i);

		for(int x = 1;x <= 4;++x)id[i][x] = ++pcnt;

		DIJ::add(id[i][1],id[i][2],c);

		DIJ::add(id[i][1],id[i][4],c);

		DIJ::add(id[i][3],id[i][2],c);

		DIJ::add(id[i][3],id[i][4],c);//cout << i << endl;

	}

	DIJ::s = ++pcnt;

	for(int i = GRAPH::lin[1];i != 0;i = GRAPH::e[i].nxt)

	{

		if(GRAPH::e[i].ty == 1)

		{

			DIJ::add(DIJ::s,id[GRAPH::e[i].id][1],0);

			DIJ::add(DIJ::s,id[GRAPH::e[i].id][3],0);

		}

	}

	for(int i = 2;i <= n;++i)idp[i] = ++pcnt;

	for(int k = 2;k <= n;++k)

	{

		for(int i = GRAPH::lin[k];i != 0;i = GRAPH::e[i].nxt)

		{

			if(GRAPH::e[i].ty == 0)

			{

				DIJ::add(id[GRAPH::e[i].id][2],idp[k],0);

				DIJ::add(id[GRAPH::e[i].id][4],idp[k],0);

			}

		}

	}

	for(int i = 1;i < p;++i)

	{

		scanf("%d%d%d",&a,&b,&c);

		TRIE::add(a,b);

	}

	TRIE::dfs1(1,1);TRIE::dfs2(1,1);//for(int i = 1;i <= p;++i)cout << TRIE::dfn[i] << " ";cout << endl;

	for(int k = 1;k <= n;++k)

	{

		tp = tp1 = tp2 = 0;//cout << " : " << k << endl;

		for(int i = GRAPH::lin[k];i != 0;i = GRAPH::e[i].nxt)

		{

			if(GRAPH::e[i].ty == 0)s1[++tp1] = i;

			if(GRAPH::e[i].ty == 1)s2[++tp2] = i;

			s[++tp] = i;

		}

		sort(s1 + 1,s1 + tp1 + 1,cmp_es_dfn);

		sort(s2 + 1,s2 + tp2 + 1,cmp_es_dfn);

		sort(s + 1,s + tp + 1,cmp_es_dfn);

		for(int i = 1;i < tp1;++i)DIJ::add(id[GRAPH::e[s1[i]].id][2],id[GRAPH::e[s1[i + 1]].id][2],0);

		for(int i = 1;i < tp2;++i)DIJ::add(id[GRAPH::e[s2[i]].id][1],id[GRAPH::e[s2[i + 1]].id][1],0);

		for(int i = 0,j = 1,x = 1;x < tp;++x)

		{

			while(i < tp1 && TRIE::dfn[GRAPH::e[s1[i + 1]].d] <= TRIE::dfn[GRAPH::e[s[x]].d])++i;

			while(j <= tp2 && TRIE::dfn[GRAPH::e[s2[j]].d] < TRIE::dfn[GRAPH::e[s[x + 1]].d])++j;

			if(1 <= i && i <= tp1 && j <= tp2)DIJ::add(id[GRAPH::e[s1[i]].id][2],id[GRAPH::e[s2[j]].id][1],TRIE::LCP(GRAPH::e[s[x]].d,GRAPH::e[s[x + 1]].d));

		}

		for(int i = 1;i < tp1;++i)DIJ::add(id[GRAPH::e[s1[i + 1]].id][4],id[GRAPH::e[s1[i]].id][4],0);

		for(int i = 1;i < tp2;++i)DIJ::add(id[GRAPH::e[s2[i + 1]].id][3],id[GRAPH::e[s2[i]].id][3],0);

		for(int i = 1,j = 0,x = 1;x < tp;++x)

		{

			while(j < tp2 && TRIE::dfn[GRAPH::e[s2[j + 1]].d] <= TRIE::dfn[GRAPH::e[s[x]].d])++j;

			while(i <= tp1 && TRIE::dfn[GRAPH::e[s1[i]].d] < TRIE::dfn[GRAPH::e[s[x + 1]].d])++i;

			if(1 <= j && j <= tp2 && i <= tp1)DIJ::add(id[GRAPH::e[s1[i]].id][4],id[GRAPH::e[s2[j]].id][3],TRIE::LCP(GRAPH::e[s[x]].d,GRAPH::e[s[x + 1]].d));

		}

	}

	DIJ::dijkstra();

	for(int i = 2;i <= n;++i)printf("%lld\n",DIJ::d[idp[i]]);

	return;

}

int main()

{

	int testcases = rd();

	while(testcases--)work();

	return 0;

}