fr.cpp

//
// File:   fs.cc
// Author: cteam008
//
// Created on October 19, 2013, 10:50 AM
//
 
#include <stdlib.h>
#include <stdio.h>
#include <iostream>
#include <vector>
#include <queue>
 
using namespace std;
 
struct node {
    unsigned int effort;
    vector<int> children;
};
 
struct edge {
    int u,v,w;
};
 
vector<node> nodes;
 
int getMinEffort(int node) {
    if (nodes[node].children.empty()) return nodes[node].effort;
    unsigned int minChildren = 0;
    for (int i = 0; i < nodes[node].children.size(); i++) {
        minChildren += getMinEffort(nodes[node].children[i]);
        if (minChildren >= nodes[node].effort) {
            return nodes[node].effort;
        }
    }
    return minChildren;
}
//
//
//
int main(int argc, char** argv) {
    int n,c,u,v,w;
    while (cin >> n >> c) {
        queue<edge> edges;
        nodes.clear();
        for (int i = 0; i <= n; i++) {
            node n;
            n.effort = 0;
            nodes.push_back(n);
        }
        nodes[c].effort = -1;
        for (int i = 1; i < n; i++) {
            edge e;
            cin >> e.u >> e.v >> e.w;
            if (e.u == c) {
                nodes[c].children.push_back(e.v);
                nodes[e.v].effort = e.w;
            } else if (e.v == c) {
                nodes[c].children.push_back(e.u);
                nodes[e.u].effort = e.w;
            } else {
                edges.push(e);
            }
        }
        while (!edges.empty()) {
            edge e = edges.front();
            edges.pop();
            if (nodes[e.v].effort != 0) {
                nodes[e.v].children.push_back(e.u);
                nodes[e.u].effort = e.w;
            } else if (nodes[e.u].effort != 0) {
                nodes[e.u].children.push_back(e.v);
                nodes[e.v].effort = e.w;
            } else {
                edges.push(e);
            }
        }
        cout << getMinEffort(c) << endl;
    }
    return (EXIT_SUCCESS);
}