#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <stack>
#include <queue>
typedef unsigned int uint;
struct Edge;
struct Node;
typedef std::vector<Edge *> Edges;
typedef std::vector<Node *> Nodes;
struct Edge {
uint visited;
int flow, capacity;
Edge* reverse;
Node* from;
Node* to;
Edge(const int capacity, Node& from, Node& to):
visited(0),
flow(0),
capacity(capacity),
reverse(NULL),
from(&from),
to(&to) {
}
bool visit(const uint visit) {
if (visited == visit)
return false;
visited = visit;
return true;
}
int available() const {
return capacity - flow;
}
};
struct Node {
uint id;
uint visited;
Node* whence;
Edge* through;
Edges in, out;
Node(uint id):
id(id),
visited(0) {
}
bool visit(const uint visit) {
if (visited == visit)
return false;
visited = visit;
return true;
}
};
struct Edge_less_available {
bool operator() (const Edge *const a, const Edge *const b) {
return a->available() < b->available();
}
};
bool touches(const Edges& edges, Node& node) {
for (Edges::const_iterator it = edges.begin(); it != edges.end(); it++)
{
Edge& edge = **it;
if (&node == edge.from)
return true;
if (&node == edge.to)
return true;
}
return false;
}
struct Graph {
int flow;
uint visit;
Node* source;
Node* sink;
Nodes nodes;
Edges edges;
Graph(const uint nNodes, const uint idSource):
flow(0),
visit(0),
source(NULL),
sink(NULL) {
for (uint idNode = 0; idNode <= nNodes + 1; idNode++)
nodes.push_back(new Node(idNode));
source = nodes[idSource];
sink = nodes[nNodes + 1];
}
~Graph() {
for (Nodes::iterator it = nodes.begin(); it != nodes.end(); it++)
delete *it;
for (Edges::iterator it = edges.begin(); it != edges.end(); it++)
delete *it;
}
void add_edge(const uint idFrom, const uint idTo, const int capacity) {
Node& from = *nodes[idFrom];
Node& to = *nodes[idTo ];
Edge* edgeFw = new Edge(capacity, from, to);
Edge* edgeBw = new Edge(capacity, to, from);
edges.push_back(edgeFw);
edges.push_back(edgeBw);
edgeFw->reverse = edgeBw;
edgeBw->reverse = edgeFw;
from.out.push_back(edgeFw);
from.in .push_back(edgeBw);
to .in .push_back(edgeFw);
to .out.push_back(edgeBw);
}
void dfs(Edges& path) {
visit++;
Node& node = *source;
bool found = dfs_next(path, node);
if (!found)
throw std::exception();
}
bool dfs_next(Edges& path, Node& node) {
if (&node == sink)
return true;
for (Edges::iterator it = node.out.begin(); it != node.out.end(); it++)
{
Edge& edge = **it;
Node& dest = *edge.to;
//~ std::cerr << "considering edge " << node.id << "-" << dest.id << ": " << edge.available() << std::endl;
if (touches(path, dest))
continue;
if (!edge.visit(visit) || edge.available() <= 0)
continue;
path.push_back(&edge);
bool result = dfs_next(path, dest);
if (result)
return true;
path.pop_back();
}
return false;
}
void sinkify() {
visit++;
Node& node = *source;
node.visit(visit);
sinkify_next(node);
}
void sinkify_next(Node& node) {
uint outEdges = 0;
for (Edges::iterator it = node.out.begin(); it != node.out.end(); it++)
{
Edge& edge = **it;
Node& dest = *edge.to;
if (!dest.visit(visit))
continue;
outEdges++;
sinkify_next(dest);
}
if (outEdges == 0)
add_edge(node.id, sink->id, 1000000);
}
void maximize() {
while (true)
{
Edges path;
try {
dfs(path);
//~ std::cerr << "path " << visit << ": " << source->id;
//~ for (Edges::iterator it = path.begin(); it != path.end(); it++)
//~ {
//~ Node* cur = (*it)->to;
//~ std::cerr << " -(" << (*it)->available() << ")- " << cur->id;
//~ }
//~ std::cerr << std::endl;
} catch (std::exception) {
break;
}
int flowIncrease;
{
Edge& edge = **std::min_element(path.begin(), path.end(), Edge_less_available());
flowIncrease = edge.available();
}
flow += flowIncrease;
for (Edges::iterator it = path.begin(); it != path.end(); it++)
{
Edge& edge = **it;
Edge& reverse = *edge.reverse;
edge.flow += flowIncrease;
reverse.flow -= flowIncrease;
}
}
}
};
int main() {
while (true)
{
uint nNodes, idSource;
std::cin >> nNodes >> idSource;
if (std::cin.fail())
break;
Graph sprink(nNodes, idSource);
for (uint i = 0; i < nNodes - 1; i++)
{
uint idFrom, idTo;
int capacity;
std::cin >> idFrom >> idTo >> capacity;
sprink.add_edge(idFrom, idTo, capacity);
}
sprink.sinkify();
//~ for (Edges::iterator it = sprink.edges.begin(); it != sprink.edges.end(); it++)
//~ std::cerr << "edge " << (*it)->from->id << " - " << (*it)->to->id << ": " << (*it)->capacity << std::endl;
sprink.maximize();
std::cout << sprink.flow << std::endl;
}
return 0;
}