#pragma comment(linker, "/STACK:1024000000,1024000000")

 #include <cstdio>

 #include <cstdlib>

 #include <cstring>

 #include <iostream>

 #include <algorithm>

 using namespace std;

 typedef unsigned long long ull;

 typedef long long ll;

 const int inf = 0x3f3f3f3f;

 const int maxn = 1e5+;

 struct

 {

     int  to,next;

 } e[maxn<<];

 int head[maxn],edge;

 void add(int x,int y)

 {

     e[edge].to = y;

     e[edge].next = head[x];

     head[x] = edge++;

 }

 int son[maxn],fa[maxn],siz[maxn],dep[maxn];

 void dfs1(int root)

 {

     siz[root] = ;

     son[root] = ;

     for (int i = head[root]; i > ; i = e[i].next)

     {

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

         {

             dep[e[i].to] = dep[root] + ;

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

             dfs1(e[i].to);

             if (siz[son[root]] < siz[e[i].to])

                 son[root] = e[i].to;

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

         }

     }

 }

 int top[maxn],pos[maxn],fp[maxn],tot;

 void dfs2(int root,int f)

 {

     top[root] = f;

     pos[root] = tot++;

     fp[pos[root]] = root;

     if (son[root]>)

         dfs2(son[root],top[root]);

     for (int i = head[root]; i > ; i = e[i].next)

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

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

 }

 ll addv[][maxn<<];

 int k;

 void pre_update(int ua,int ub,int cho)

 {

     int f1 = top[ua];

     int f2 = top[ub];

     while (f1 != f2)

     {

         if (dep[f1] < dep[f2])

             swap(f1,f2),swap(ua,ub);

         addv[cho][pos[f1]] += k;

         addv[cho][pos[ua]+] -= k;

         ua = fa[f1];

         f1 = top[ua];

     }

     if (dep[ua] > dep[ub])

         swap(ua,ub);

     if (cho == )

         addv[cho][pos[ua]] += k,addv[cho][pos[ub]+] -= k;

     if (cho == )

         addv[cho][pos[son[ua]]] += k,addv[cho][pos[ub]+] -= k;

 }

 int n,m,d[maxn][],link[maxn];

 void init()

 {

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

     int root = ;

     dep[root] = fa[root] = ;

     edge = tot = ;

     memset(head,,sizeof(head));

     memset(siz,,sizeof(siz));

     memset(addv,,sizeof(addv));

     for (int i = ; i < n; i++)

     {

         int u,v;

         scanf ("%d%d",&u,&v);

         d[i][] = u;

         d[i][] = v;

         add(u,v),add(v,u);

     }

     dfs1(root);

     dfs2(root,root);

     for (int i = ; i < n; i++)

     {

         if (dep[d[i][]] < dep[d[i][]])

             swap(d[i][],d[i][]);

         link[d[i][]] = i;

     }

 }

 ll ans1[maxn],ans2[maxn];

 int main(void)

 {

     //freopen("in.txt","r",stdin);

     int t;

     int cas = ;

     scanf ("%d",&t);

     while (t--)

     {

         init();

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

         {

             char op[];

             int u,v;

             scanf ("%s%d%d%d",op,&u,&v,&k);

             pre_update(u,v,op[]-'');

         }

         for (int i = ; i <= n; i++)

         {

             addv[][i] += addv[][i-];

             addv[][i] += addv[][i-];

             ans1[fp[i]] = addv[][i];

             ans2[link[fp[i]]] = addv[][i];

         }

         printf("Case #%d:\n",cas++);

         printf("%I64d",ans1[]);

         for (int i = ; i <= n; i++)

         {

             printf(" %I64d",ans1[i]);

         }

         printf("\n");

         if (n>)

             printf("%I64d",ans2[]);

         for (int i = ; i < n; i++)

         {

             printf(" %I64d",ans2[i]);

         }

         printf("\n");

     }

     return ;

 }