救救我！对拍了一天没有任何错误，70 pts，WA。

假如有无意义回复我会马上拉黑。

//use c++11!!
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
#include<queue>
using namespace std;
int n,m,k,dfn[20005],sign,p[20005][20],d[20005],tot,ls[1000005],rs[1000005],height[50005],st[50005],top,fl[50005],fr[50005],rd[50005],cd[50005];
long long dis[1000005];
struct fEdge {
	int from,to,len,str,id;
	bool operator <(const fEdge yy) const {
		return dfn[str]<dfn[yy.str];
	}
};
namespace Trie {
	struct Edge {
		int to,next,value;
	}e[50005];
	int h[50005],cnt;
	void DFS(int x){
		dfn[x]=++sign;
		for(int i=1;i<=15;i++)p[x][i]=p[p[x][i-1]][i-1];
		for(int i=h[x];i;i=e[i].next){
			int y=e[i].to;
			p[y][0]=x,d[y]=d[x]+1,DFS(y);
		}
	}
	int LCA(int x,int y){
		if(d[x]<d[y])swap(x,y);
		for(int i=15;i>=0;i--)if(d[p[x][i]]>=d[y])x=p[x][i];
		if(x==y)return d[x];
		for(int i=15;i>=0;i--)if(p[x][i]^p[y][i])x=p[x][i],y=p[y][i];
		return d[p[x][0]];
	}
	void Init(){
		for(int i=1,x,y,z;i<k;i++){
			scanf("%d%d%d",&x,&y,&z);
			e[++cnt]={y,h[x],z},h[x]=cnt;
		}
		DFS(1);
	}
	void Clear(){
		cnt=0;
		memset(h,0,sizeof(h));
	}
};
vector<fEdge> fg[50005];
vector<int> g[1000005],val[1000005];
void Add_Edge(int x,int y,int z){
	g[x].push_back(y),val[x].push_back(z);
	//cout<<x<<' '<<y<<' '<<z<<endl;
}
void Build(int &p,int &q,int l,int r){
	if(!p)p=++tot;
	if(!q)q=++tot;
	if(l==r)return ;
	int mid=(l+r)/2;
	Build(ls[p],ls[q],l,mid),Add_Edge(ls[p],p,0),Add_Edge(q,ls[q],0);
	Build(rs[p],rs[q],mid+1,r),Add_Edge(rs[p],p,0),Add_Edge(q,rs[q],0);
}
void Update(int p,int l,int r,int x,int y,int flag){
	if(l==r){
		if(flag)Add_Edge(p,y,0);
		else Add_Edge(y,p,0);
		return ;
	}
	int mid=(l+r)/2;
	if(x<=mid)Update(ls[p],l,mid,x,y,flag);
	else Update(rs[p],mid+1,r,x,y,flag);
}
void Add(int p,int l,int r,int x,int y,int z,int flag){
	if(x<=l&&r<=y){
		if(flag)Add_Edge(z,p,0);
		else Add_Edge(p,z,0);
		return ;
	}
	int mid=(l+r)/2;
	if(x<=mid)Add(ls[p],l,mid,x,y,z,flag);
	if(mid<y)Add(rs[p],mid+1,r,x,y,z,flag);
}
struct Node{
	int num,dist;
	bool operator <(const Node yy) const {
		return dist>yy.dist;
	}
};
void Dijkstra(){
	memset(dis,0x3f,sizeof(dis));
	priority_queue<Node> q;
	dis[2*m+1]=0;
	q.push({2*m+1,0});
	while(!q.empty()){
		int now=q.top().num;
		if(q.top().dist!=dis[now]){
			q.pop();
			continue;
		}
		q.pop();
		for(int i=0;i<g[now].size();i++){
			int y=g[now][i],v=val[now][i];
			if(dis[y]>dis[now]+v){
				dis[y]=dis[now]+v;
				q.push({y,dis[y]});
			}
		}
	}
	for(int i=2;i<=n;i++){
		long long ans=0x3f3f3f3f3f3f3f3fll;
		for(fEdge y:fg[i]){
			if(y.to==i)ans=min(ans,dis[y.id+m]);
		}
		printf("%lld\n",ans);
	}
}
void Clear(){
	for(int i=1;i<=tot;i++)g[i].clear(),val[i].clear(),ls[i]=rs[i]=0;
	for(int i=1;i<=n;i++)fg[i].clear(),rd[i]=cd[i]=0;
	memset(p,0,sizeof(p));
	Trie::Clear();
	tot=sign=0;
}
int main() {
	//freopen("test.in","r",stdin);
	//freopen("wrong.out","w",stdout);
	int kase;
	scanf("%d",&kase);
	while(kase--){
		scanf("%d%d%d",&n,&m,&k);
		tot=2*m+1;
		for(int i=1,x,y,z,w;i<=m;i++){
			scanf("%d%d%d%d",&x,&y,&z,&w);
			fg[x].push_back({x,y,z,w,i}),fg[y].push_back({x,y,z,w,i});
			Add_Edge(i,i+m,z),rd[y]++,cd[x]++;
			if(x==1)Add_Edge(tot,i,0);
		}
		Trie::Init();
//		if(kase>1){
//			Clear();
//			continue;
//		}
		for(int i=1;i<=n;i++){
			//cout<<i<<endl;
			if(!rd[i]||!cd[i])continue;
			int all=fg[i].size();
			int rootto=++tot,rootfrom=++tot;
			Build(rootto,rootfrom,1,all);
			sort(fg[i].begin(),fg[i].end());
			for(int j=0;j<all;j++){
				if(fg[i][j].from==i)Update(rootfrom,1,all,j+1,fg[i][j].id,1);
				else Update(rootto,1,all,j+1,fg[i][j].id+m,0);
			}
			//cout<<i<<endl;
			for(int j=1;j<all;j++)height[j]=Trie::LCA(fg[i][j-1].str,fg[i][j].str);
			st[top=0]=0;
			for(int j=1;j<all;j++){
				while(top&&height[st[top]]>=height[j])top--;
				fl[j]=st[top]+1,st[++top]=j;
			}
			st[top=0]=all;
			for(int j=all-1;j>0;j--){
				while(top&&height[st[top]]>=height[j])top--;
				fr[j]=st[top]-1,st[++top]=j;
			}
			for(int j=1;j<all;j++){
				int a=++tot,b=++tot;
				Add_Edge(a,b,height[j]);
				Add(rootto,1,all,fl[j],j,a,0);
				Add(rootfrom,1,all,j+1,fr[j]+1,b,1);
				a=++tot,b=++tot;
				Add_Edge(a,b,height[j]);
				Add(rootfrom,1,all,fl[j],j,b,1);
				Add(rootto,1,all,j+1,fr[j]+1,a,0);
			//	printf("i=%d j=%d height=%d fl=%d fr=%d\n",i,j,height[j],fl[j],fr[j]); 
			}
		} 
		Dijkstra();
		Clear();
//		cout<<"kase"<<kase<<endl;
	}
}