// Solution for problem High Spies,  BAPC 2006
// Includes check on correctness input
//
// Rudy van Vliet              1 September 2006

#include <iostream>
using namespace std;

const int MinWeight = 0,
          MaxWeight = 1000,
          MinN = 2,
          MaxN = 10000;

struct AdjElt
{ int To;
  int Weight,
      WeightBack;
  AdjElt *Next;
};

AdjElt **Neighbours;

//***************************************************************************

void AddEdgeToTree (int From, int To, int Weight, int WeightBack)
{ AdjElt *Adj1;

  Adj1 = new AdjElt;
  Adj1 -> To = To;
  Adj1 -> Weight = Weight;
  Adj1 -> WeightBack = WeightBack;
  Adj1 -> Next = Neighbours[From];
  Neighbours[From] = Adj1;
 
}  // AddEdgeToTree

//***************************************************************************

bool ReadTree (int &N, int &S, int &E)
{ int i,
      From, To,
      Weight1, Weight2;
  bool OK;

  OK = true;

  cin >> N;
  Neighbours = new AdjElt* [N+1];
  for (From=1;From<=N;From++)
  { Neighbours[From] = NULL;
  }

  if ((N<MinN) || (N>MaxN))
  { cout << "N=" << N << "\n";
    OK = false;
  }

  for (i=1;i<=N-1;i++)
  { cin >> From >> To >> Weight1 >> Weight2;
    if ((1<=From)&&(From<=N)&&(1<<To)&&(To<=N)
        &&(Weight1>=MinWeight)&&(Weight1<=MaxWeight)
        &&(Weight2>=MinWeight)&&(Weight2<=MaxWeight))
    // we have to check From and To before we can add an edge;
    // for simplicity, we also check Weight1 and Weight2;
    { AddEdgeToTree (From, To, Weight1, Weight2);
      AddEdgeToTree (To, From, Weight2, Weight1);
    }
    else
    { cout << "From=" << From << "  To=" << To
           << "  Weigth1=" << Weight1 << "  Weight2=" << Weight2 << "\n";
      OK = false;
    }
  }

  cin >> S >> E;
  if ((S<1)||(S>N)||(E<1)||(E>N)||(S==E))
  { OK = false;
    cout << "S=" << S << " and E=" << E << "\n";
  }

  return OK;
  
}  // ReadTree

//***************************************************************************

void Union (int i, int j, int *Parent, int *Height)
  // merge the trees with roots i and j
{
  if (Height[i]<Height[j])
    Parent[i] = j;
  else
    if (Height[i]>Height[j])
      Parent[j] = i;
    else  // equal height
    { Parent[j] = i;
      Height[i] ++;
    }

}  // Union

//***************************************************************************

int Find (int i, int *Parent)
  // pre: 1<=i<=N
{ int Walk;

  Walk = i;
  while (Parent[Walk]>0)
    Walk = Parent[Walk];

  return Walk;

}  // Find

//***************************************************************************

bool CheckTree (int N, int S, int E)
  // check if we really have a tree,
  // for which a transport schedule exists
{ int *Parent,
      *Height;
  bool OK,
       SIsLeaf,
       EIsLeaf;
  int i,
      From, To,
      Root1, Root2,
      NrNeighb,
      SumWeightOut, SumWeightIn,
      WeightOut, WeightIn;
  AdjElt *Adj1;

  OK = true;

    // first, check if we really have a tree
  Parent = new int[N+1];
  Height = new int[N+1];
  for (i=1;i<=N;i++)
  { Parent[i] = -1;
    Height[i] = 1;
  }
    // examine all edges in the graph
  for (From=1;(From<=N)&&OK;From++)
  { Adj1 = Neighbours[From];
    while (OK && (Adj1!=NULL))
    { To = Adj1 -> To;
      if (To==From)  // a loop
      { OK = false;
        cout << "The graph contains a loop (" << From << "," << To << ").\n";
      }
      else
        if (To>From)  // this way we examine only one of two directions
        { Root1 = Find (From, Parent);
          Root2 = Find (To, Parent);
          if (Root1==Root2)  // a cycle
          { OK = false;
            cout << "The edge (" << From << "," << To
                 << ") closes a cycle in the graph.\n";
          }
          else
            Union (Root1, Root2, Parent, Height);
        }
      if (OK)
        Adj1 = Adj1 -> Next;
    }
  }
  delete [] Parent;
  delete [] Height;

  if (OK)
    // check if the tree satisfies all conditions on the weights of
    // the internal nodes
  { SIsLeaf = false;  // we have not yet established
    EIsLeaf = false;  // that S and E are leaves
    for (From=1;(From<=N)&&OK;From++)
    { NrNeighb = 0;
      SumWeightOut = 0;
      SumWeightIn = 0;
      Adj1 = Neighbours[From];
      while (Adj1!=NULL)
      { NrNeighb ++;
        SumWeightOut += Adj1 -> Weight;
        SumWeightIn += Adj1 -> WeightBack;
        Adj1 = Adj1 -> Next;
      }
      if (NrNeighb>=2)  // an internal node
      { if (SumWeightOut == SumWeightIn)
        {  // for each neighbour, check if the load coming in from that
           // neighbour can go out to the other neighbours
          Adj1 = Neighbours[From];
          while (OK && (Adj1!=NULL))
          { WeightOut = Adj1 -> Weight;
            WeightIn = Adj1 -> WeightBack;
            if (WeightIn > SumWeightOut - WeightOut)
            { OK = false;
              cout << "The weight " << WeightIn << " over edge ("
                   << Adj1->To << "," << From 
                   << ") cannot go out to the other neighbours.\n";
            }
            else
              Adj1 = Adj1 -> Next;
          }
        }
        else
        { OK = false;
          cout << "For node " << From 
               << " is SumWeightOut = " << SumWeightOut
               << " and SumWeightIn = " << SumWeightIn << ".\n";
        }
      }  // if an internal node
      else // <= 1 neighbour; because the graph is a tree (we have
           // checked that already) and thus connected, From must be a leaf
      { if (From==S)
          SIsLeaf = true;
        else
          if (From==E)
            EIsLeaf = true;
      }
        
    }  // for all nodes
  }  // OK

  if (OK)
  { if (!SIsLeaf)
    { OK = false;
      cout << "S=" << S << " is not a leaf.\n";
    }
    if (!EIsLeaf)
    { OK = false;
      cout << "E=" << E << " is not a leaf.\n";
    }
  }

  return OK;

}  // CheckTree

//***************************************************************************

bool Search (int Curr, int E, bool *Visited)
 // try to find a path in the tree from Curr to E
 // pre: Curr is not yet visited
{ bool Found;
  AdjElt *Adj0,
         *Adj1;
  int To;

  Visited [Curr] = true;
  Found = false;
  Adj0 = NULL;  // predecessor of Adj1
  Adj1 = Neighbours[Curr];
  while ((Adj1!=NULL)&&(!Found))
  { To = Adj1 -> To;
    if (To==E)
      Found = true;
    else
      if (!(Visited[To]))
        Found = Search (To, E, Visited);
      // else: already visited: we do not climb back in the tree

    if (Found)  // move the edge from Curr to To to the front of
                // the adjacency list of Curr
    { if (Adj0!=NULL)
      { Adj0 -> Next = Adj1 -> Next;
        Adj1 -> Next = Neighbours[Curr];
        Neighbours[Curr] = Adj1;
      }
      // else: Adj1 was already the first edge in the adjacency list
    }
    else
    { Adj0 = Adj1;
      Adj1 = Adj1 -> Next;
    }

  }  // while

  return Found;
  
} // Search

//***************************************************************************

bool FindPath (int N, int S, int E)
{ bool *Visited,
       Found;
  int From;

  Visited = new bool[N+1];
  for (From=1;From<=N;From++)
    Visited[From] = false;

  Found = Search (S, E, Visited);
    // should be the case, because the graph is connected
    
  delete [] Visited;

  return Found;
}  // FindPath

//***************************************************************************

int Maxim (int a, int b)
{
  if (a>b)
    return a;
  else
    return b;

}  // Maxim

//***************************************************************************

int Minim (int a, int b)
{
  if (a<b)
    return a;
  else
    return b;

}  // Minim

//***************************************************************************

int DetermineMin (int S, int E)
 // pre: path from S to E is stored in first positions of
 //   the adjacency list
{ int Min,
      Prev, Curr, To,
      WeightCurrToTo, WeightToToCurr,
      WeightPrevToCurr, WeightCurrToPrev,
      MaxPrevToOthers, MinToToOthers,
      SumWeightOut;
  AdjElt *Adj1;

  Prev = 0;
  Curr = S;
  do
  { Adj1 = Neighbours[Curr];
    To = Adj1 -> To;
    WeightCurrToTo = Adj1 -> Weight;
    WeightToToCurr = Adj1 -> WeightBack;
    if (Curr==S)
      Min = Adj1 -> Weight;
    else
    {  // check how much of the capacity from Curr to To we have to 
       // reserve for the transport from Prev

       // first sum all outgoing weight from Curr
      SumWeightOut = Adj1 -> Weight;
      Adj1 = Adj1 -> Next;
      while (Adj1!=NULL)
      { SumWeightOut += Adj1 -> Weight;
        Adj1 = Adj1 -> Next;
      }

       // maximize the weight from (Prev To Curr) that we can send to other
       // places than To;

       // first calculate the capacity of all edges to these other places
      MaxPrevToOthers = SumWeightOut - WeightCurrToPrev - WeightCurrToTo;

       // we cannot always use this full capacity for the weight from
       // (Prev to Curr); we may need part of this capacity for the weight
       // from To to Curr
      MinToToOthers = WeightToToCurr - WeightCurrToPrev;
      if (MinToToOthers>0)
        MaxPrevToOthers -= MinToToOthers;

       // we can send at most MaxPrevToOthers of the amount from Prev to Curr
       // to these other places; especially try to send the Min containers
       // to these other places; what is left, must be sent to To
      Min = Maxim (0, Min-MaxPrevToOthers);

    }  // Curr is different from S

    Prev = Curr;
    Curr = To;
    WeightPrevToCurr = WeightCurrToTo;
    WeightCurrToPrev = WeightToToCurr;

  } while (Curr!=E);

  return Min;

}  // DetermineMin

//***************************************************************************

int DetermineMax (int S, int E)
 // pre: path from S to E is stored in first positions of
 //   the adjacency list
{ int Max,
      Prev, Curr, To,
      A,
      SumWeightOut,
      WeightOut, WeightIn,
      Extra;
  AdjElt *Adj1;

  Prev = 0;
  Curr = S;
  do
  { Adj1 = Neighbours[Curr];
    To = Adj1 -> To;
    if (Curr==S)
      Max = Adj1 -> Weight;
    else
    { Max = Minim (Max, Adj1 -> Weight);
       // check if we can really reserve an amount Max of the capacity
       // from Curr to To for the transport from Prev

       // first sum all outgoing weight from Curr
      SumWeightOut = Adj1 -> Weight;
      Adj1 = Adj1 -> Next;
      while (Adj1!=NULL)
      { SumWeightOut += Adj1 -> Weight;
        Adj1 = Adj1 -> Next;
      }

       // for each node A different from Prev and To, compute the difference
       // between the Weight from A to Curr and
       // the Weight from Curr to all nodes different from A;
       // this amount may be reserved for the transport from Prev via
       // Curr to To.
      Adj1 = Neighbours [Curr];  // the edge to To; skip this
      Adj1 = Adj1 -> Next;
      while (Adj1!=NULL)
      { A = Adj1->To;
        if (A != Prev)
        { WeightOut = Adj1->Weight;
          WeightIn = Adj1->WeightBack;  // the Weight from A to Curr
          Extra = SumWeightOut - WeightOut - WeightIn;
          Max = Minim (Max, Extra);
        }
        Adj1 = Adj1 -> Next;
      }  // while Adj1!=NULL

    }  // Curr is different from S

    Prev = Curr;
    Curr = To;

  } while (Curr!=E);

  return Max;

}  // DetermineMax

//***************************************************************************

void DeleteTree (int N)
{ int From;
  AdjElt *Adj1, *Adj2;

  for (From=1;From<=N;From++)
  { Adj1 = Neighbours[From];
    while (Adj1 != NULL)
    { Adj2 = Adj1 -> Next;
      delete Adj1;
      Adj1 = Adj2;
    }
    Neighbours[From] = NULL;
  }
  delete [] Neighbours;

}  // DeleteTree

//***************************************************************************

int main ()
{ int NrInst, i,
      N, S, E,
      Max, Min;
  bool OK;

  cin >> NrInst;
  for (i=1;i<=NrInst;i++)
  { OK = ReadTree (N, S, E);
// cout << "Tree read.\n";
    if (OK)
      if (CheckTree (N, S, E))  // a correct tree
      {
// cout << "Correct Tree.\n";
        if (FindPath (N, S, E))
         // should be the case
        {
// cout << "Path Found.\n";
          Min = DetermineMin (S, E);
// cout << "Min Determined.\n";
          Max = DetermineMax (S, E);
// cout << "Max Determined.\n";
          if (Min<=Max)  // just for security ...
            cout << Min << " " << Max << "\n";
          else
            cout << "Min=" << Min << " and Max=" << Max << ".\n";
        }
        else
          cout << "No path from S=" << S << " to E=" << E << ".\n";
      }
    
    DeleteTree (N);
  }  // for

  return 0;

}

