// -*- compile-command: "g++ -c m.cpp" -*-
#include <algorithm>
#include <cassert>
#include <cmath>
#include <cstdlib>
#include <iostream>
#include <locale>
#include <map>
#include <set>
#include <sstream>
#include <string>
#include <vector>
#include <ctime>
#include <numeric>

#define DBG(x) cout << #x << " = " << x << endl;
#define FOR(i, n) for (i = 0; i != (n); ++i)
#define FOREACH(i, c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); ++i)
#define ALL(c) (c).begin(), (c).end()
#define IN(e, c) ((c).find(e) != (c).end())
#define ALLARRAY(a) (a), ((a) + sizeof(a) / sizeof(a[0]))
#define EXISTS(x, A, pred) ({ typeof((A).begin()) x = (A).begin(); for (; x != (A).end(); ++x) if (pred) break; x != (A).end(); })
#define FORALL(x, A, pred) (! EXISTS(x, A, !(pred)))
#define MEMSET(x, v) memset(x, v, sizeof(x))


typedef long long i64;

using namespace std;

int m;
vector<int> adj[128];
vector<int> cst[128];

i64 b[128][128];

const i64 INF = 0x7fffffffLL * 100;


void dfs(int nn, int n) {
  int i, j, k;
  for (i = 0; i < adj[n].size(); ++i) if (adj[n][i] != nn) {
    dfs(n, adj[n][i]);

    for (j = m; j >= 0; --j) {
      for (k = 0; k <= j; ++k) 
        b[n][j] = min(b[n][j], b[n][j-k] + b[adj[n][i]][k] + !!k * cst[n][i]);
    }
  }
}

struct HighwayBuilding {
  int getMaxCities(int m_, int r, vector <string> gs, int bm) {
    m = m_;
    int i, j;
    for (i = 0; i < gs.size(); ++i) {
      replace(ALL(gs[i]), ',', ' ');
      istringstream iss(gs[i]);
      int f, t, c;
      while (iss >> f >> t >> c) {
        adj[f].push_back(t);
        cst[f].push_back(c);
        adj[t].push_back(f);
        cst[t].push_back(c);
      }
    }

    for (i = 0; i < m; ++i)
      for (j = 2; j <= m; ++j) b[i][j] = INF;
    
    dfs(-1, r);

    for (i = 1; i < m && b[r][i+1] <= bm; ++i);
    return i - 1;
  }
};