#include <iostream>
#include <queue>
using namespace std;
const int MAXN=1000;
const int lmax=199999999;
typedef struct
{
int v; //指向的下一个顶点"to"
int next; //"from"指向的另一条边
int cost; //当前"from"所指向的边的权
}Edge;
Edge e[MAXN];
int p[MAXN];
int Dis[MAXN];
bool vist[MAXN];
queue<int> q;
int m,n; //点,边
void grap() //构造图
{
int i;
int eid=0;
memset(vist,0,sizeof(vist));
memset(p,-1,sizeof(p));
fill(Dis,Dis+MAXN,lmax);
for(i=0;i<n;++i)
{
int from,to,cost,logo;
scanf("%d%d%d%d",&from,&to,&logo,&cost);
e[eid].next=p[from];
e[eid].v=to;
if(logo==0)
e[eid].cost=-cost;
else if(logo==1)
e[eid].cost=cost;
p[from]=eid++;
}
}
void SPF(int End)
{
grap();
int Start=1; //1为指定起点
Dis[Start]=0;
vist[Start]=true;
q.push(Start);
while (!q.empty())
{
int t=q.front();
q.pop();
vist[t]=false;
int j;
for (j=p[t];j!=-1;j=e[j].next)
{
int w=e[j].cost;
if (w+Dis[t]<Dis[e[j].v])
{
Dis[e[j].v]=w+Dis[t];
if (!vist[e[j].v])
{
vist[e[j].v]=true;
q.push(e[j].v);
}
}
}
}
printf("%d\n",Dis[End]);
}
int main()
{
int cases,End; //end 要求的接点
cin>>cases;
while(cases--)
{
cin>>m>>n>>End;
SPF(End);
}
return 0;
}
