#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 nx[500010];
ll pos[500010];
ll a[500010],b[500010];
ll rt[500010],cur;
ll t[500010*40];
ll ls[500010*40];
ll rs[500010*40];
const ll lim=1000000000;
void go(ll l,ll r,ll &p,ll rt0,ll num,ll id){
    if(!p)p=++cur;t[p]=id;
    if(l==r)return;
    ll mid=l+r>>1;
    // cout<<l<<" "<<r<<" "<<num<<" "<<id<<endl;
    if(mid>=num){
        rs[p]=rs[rt0];
        go(l,mid,ls[p],ls[rt0],num,id);
    }else{
        ls[p]=ls[rt0];
        go(mid+1,r,rs[p],rs[rt0],num,id);
    }
}
ll get(ll l,ll r,ll p,ll num){
    if(!p)return k+1;
    if(num<=l)return t[p];
    ll mid=l+r>>1,res=n+1;
    if(mid>=num)res=min(res,get(l,mid,ls[p],num));
    if(mid<lim)res=min(res,get(mid+1,r,rs[p],num));
    return res;
}
bool vis[500010];
set<ll>st[500010];
int main(){
    T=d;while(T--){
        n=d,m=d,k=d;
        cnt=0;f(i,1,n)hd[i]=nx[i]=0,vis[i]=0;
        f(i,1,m)pos[i]=0,st[i].clear();
        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,st[a[i]].insert(i);
        for(int i=k;i>=1;i--){
            nx[i]=pos[a[i]];
            pos[a[i]]=i;
        }
        rt[n+1]=++cur;
        for(int i=k;i>=1;i--){
            if(!nx[i])go(1,lim,rt[i],rt[n+1],b[i],i);
            else go(1,lim,rt[i],rt[nx[i]],b[i],i);
        }
        while(!q.empty())q.pop();
        f(i,1,n)dis[i]={k+1,114514};
        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(t==0){t=pos[c];if(!t)continue;}
                if(a[t]==c&&dis[u].w+w<=b[t]){id=t,nw=w+dis[u].w;}
                else{
                    auto qwq=st[c].upper_bound(t);
                    if(qwq==st[c].end())continue;t=*qwq;
                    // if(u==2&&v==3)cout<<"ooo   "<<t<<" "<<w<<endl;
                    id=get(1,lim,rt[t],w);if(id>k)continue;
                    nw=w;
                    // id=-1;
                    // f(j,t+1,k){
                    //     if(a[j]==c&&b[j]>=w){id=j,nw=w;break;}
                    // }if(id==-1)continue;
                }//cout<<id<<" "<<nw<<endl;
                if((val){id,nw}<dis[v]){
                    dis[v]={id,nw};
                    q.push({v,dis[v]});
                }
            }
        }
        // f(i,1,n)cout<<dis[i].r<<" "<<dis[i].w<<endl;
        f(i,1,n)cout<<vis[i];cout<<endl;
        f(i,1,cnt)e[i]={0,0,0,0,0};
        f(i,1,cur)t[i]=ls[i]=rs[i]=0;cur=0;
        f(i,1,n+1)rt[i]=0;
    }
	return 0;
}
/*
2
5 6 4
1 2 1 30
2 3 1 50
2 5 5 50
3 4 6 10
2 4 5 30
2 5 1 40
1 70
6 100
5 40
1 300
5 6 4
1 2 1 30
2 3 1 50
2 5 5 50
3 4 6 10
2 4 5 30
2 5 1 40
1 70
6 100
5 40
1 30


1        
5 3 2   
1 3 1 99
1 4 1 1000
3 4 1 9  
1 101
1 1
*/