#include<bits/stdc++.h>
using namespace std;
#define ll int
#define f(i,a,b) for(int i=a;i<=b;i++)
ll rd(){
	ll x=0,f=1;char c=getchar();
	while(!isdigit(c)){
		if(c=='-')f=-1;
		c=getchar();
	}while(isdigit(c)){
		x=x*10+c-'0';
		c=getchar();
	}return x*f;
}
#define d rd()
ll T,n,m,k;
struct edge{
    ll u,v,w,c,nx;
}e[1000010];
ll hd[500010],cnt;
void add(ll u,ll v,ll w,ll c){
    e[++cnt]={u,v,w,c,hd[u]};hd[u]=cnt;
}struct val{
    ll r,w;
};
bool operator < (val a,val b){
    if(a.r!=b.r)return a.r<b.r;
    return a.w<b.w;
}
struct node{ll u;val w;};
bool operator <(node a,node b){return b.w<a.w;}
priority_queue<node>q;
val dis[500010];
ll a[500010],b[500010];
bool vis[500010];
int main(){
    T=d;while(T--){
        n=d,m=d,k=d;
        cnt=0;f(i,1,n)hd[i]=0,vis[i]=0;
        f(i,1,m){
            ll u=d,v=d,c=d,w=d;
            add(u,v,w,c),add(v,u,w,c);
        }f(i,1,k)a[i]=d,b[i]=d;
        while(!q.empty())q.pop();
        f(i,1,n)dis[i]={k+1,0};
        dis[1]={0,0};q.push({1,dis[1]});
        while(!q.empty()){
            ll u=q.top().u;q.pop();
            if(vis[u])continue;vis[u]=1;
            for(int i=hd[u];i;i=e[i].nx){
                ll v=e[i].v,w=e[i].w,c=e[i].c;
                ll t=dis[u].r,id,nw;
                if(a[t]==c&&dis[u].w+w<=b[t]){id=t,nw=w+dis[u].w;}
                else{
                    id=-1;
                    f(j,t+1,k){
                        if(a[j]==c&&b[j]>=w){id=j,nw=w;break;}
                    }if(id==-1)continue;
                }
                if((val){id,nw}<dis[v]){
                    dis[v]={id,nw};
                    q.push({v,dis[v]});
                }
            }
        }
        f(i,1,n)cout<<vis[i];cout<<endl;
        if(n>=12&&!vis[12]){
            // f(i,40,k)cout<<a[i]<<" "<<b[i]<<"  ";cout<<endl;
            f(i,1,15)cout<<dis[i].r<<" "<<dis[i].w<<endl;
            for(int i=hd[12];i;i=e[i].nx){
                cout<<e[i].u<<" "<<e[i].v<<" "<<e[i].c<<" "<<e[i].w<<endl;
            }puts("");
            for(int i=hd[6];i;i=e[i].nx){
                cout<<e[i].u<<" "<<e[i].v<<" "<<e[i].c<<" "<<e[i].w<<endl;
            }
            break;
        }
        f(i,1,cnt)e[i]={0,0,0,0,0};
    }
	return 0;
}
/*
1100010010101011011011000000011000001100001000
1100010010111011011011000000011000001100001000
1 154  1 192  2 43  3 2  3 41  3 59  5 84  2 29  4 36  4 8  2 193  1 109  2 117  2 3  2 95  3 60  2 35  3 83  2 41  2 13  5 86  5 154  2 4  1 53  3 17
*/