/*
 * @Author: Floze3
 * @Date: 2024-10-15 11:11:34
 * @LastEditors: Floze3 [email protected]
 * @LastEditTime: 2024-10-15 11:13:59
 * @FilePath: /qoj/1271.cpp
 * @Description: Coding
 * Never Be Alone
 */
#include <bits/stdc++.h>
#define mp(x, y) std::make_pair(x, y)
#define mt std::make_tuple
#define eb emplace_back
#define fi first
#define se second
#define all(s) s.begin(), s.end()
#define rall(x) s.rbegin(), s.rend()
#define file(name)                 \
  freopen(name ".in", "r", stdin); \
  freopen(name ".out", "w", stdout);
#define fs(x) std::fixed << std::setprecision(x)
#define lowbit(x) (x & -x)
#define il inline
#define Avada_Kedavra return 0
#define _IOS                        \
  std::ios::sync_with_stdio(false); \
  std::cin.tie(nullptr), std::cout.tie(nullptr)
#define RANDOM_SEED std::chrono::steady_clock::now().time_since_epoch().count()
#define popcount __builtin_popcount
#define popcountll __builtin_popcountll
#define multitask    \
  int _; io.read(_); \
  while (_--)

namespace TYPEDEF {

using i64 = long long;
using u64 = unsigned long long;
using u32 = unsigned int;
using i128 = __int128;
using pii = std::pair<int, int>;
using pi64 = std::pair<i64, i64>;
using vi = std::vector<int>;
using vi64 = std::vector<i64>;
using vu64 = std::vector<u64>;
using vpii = std::vector<pii>;
using vpi64 = std::vector<pi64>;
using si = std::stack<int>;
using si64 = std::stack<i64>;
using su64 = std::stack<u64>;
using spii = std::stack<pii>;
using spi64 = std::stack<pi64>;
using qi = std::queue<int>;
using qi64 = std::queue<i64>;
using qu64 = std::queue<u64>;
using qpii = std::queue<pii>;
using qpi64 = std::queue<pi64>;
using siset = std::set<int>;
using si64set = std::set<i64>;
using su64set = std::set<u64>;
using spiiset = std::set<pii>;
using spi64set = std::set<pi64>;
using str = std::string;
using vstr = std::vector<str>;

} // namespaec TYPEDEF

using namespace TYPEDEF;

struct IO {
  #define MAXSIZE (1 << 20)
  #define isdigit(x) (x >= '0' && x <= '9')
  char buf[MAXSIZE], *p1, *p2, pbuf[MAXSIZE], *pp;
#ifndef ONLINE_JUDGE  // 调试，可显示字符
#else
  IO() : p1(buf), p2(buf), pp(pbuf) {}
  ~IO() { fwrite(pbuf, 1, pp - pbuf, stdout); }
#endif
  char gc() {
#ifndef ONLINE_JUDGE  // 调试，可显示字符
    return getchar();
#endif
    if (p1 == p2) p2 = (p1 = buf) + fread(buf, 1, MAXSIZE, stdin);
    return p1 == p2 ? ' ' : *p1++;
  }
  il bool blank(char ch) { return ch == ' ' || ch == '\n' || ch == '\r' || ch == '\t'; }
  template <typename T> il void read(T &x) {
    double tmp = 1; bool sign = 0; x = 0;
    char ch = gc();
    for (; !isdigit(ch); ch = gc()) if (ch == '-') sign = 1;
    for (; isdigit(ch); ch = gc()) x = x * 10 + (ch - '0');
    if (ch == '.')
      for (ch = gc(); isdigit(ch); ch = gc()) tmp /= 10.0, x += tmp * (ch - '0');
    if (sign) x = -x;
  }
  il void read(char *s) {
    char ch = gc();
    for (; blank(ch); ch = gc());
    for (; !blank(ch); ch = gc()) *s++ = ch;
    *s = 0;
  }
  il void read(char &c) { for (c = gc(); blank(c); c = gc()); }
  il void read(str &s) {
    s.clear(); char ch = gc();
    for (; blank(ch); ch = gc());
    for (; !blank(ch); ch = gc()) s += ch;
  }
  template<typename T, typename... Args> il void read(T &x, Args&... args) { read(x), read(args...); }
  il void push(const char &c) {
#ifndef ONLINE_JUDGE  // 调试，可显示字符
    putchar(c);
#else
    if (pp - pbuf == MAXSIZE) fwrite(pbuf, 1, MAXSIZE, stdout), pp = pbuf;
    *pp++ = c;
#endif
  }
  template <typename T> il void write(T x) {
    if (x < 0) x = -x, push('-');  // 负数输出
    static int sta[40];
    int top = 0;
    do sta[top++] = x % 10, x /= 10; while (x);
    while (top) push(sta[--top] + '0');
  }
  il void write(double x, int k = 6) {
    if (x < 0) x = -x, push('-');  // 负数输出
    static int sta[40];
    int n = pow(10, k), top = 0;
    i64 nx = (i64)x, y = i64(x * n) % n;
    write(nx, '.');
    for (int i = 0; i < k; i++) sta[++top] = y % 10, y /= 10;
    while (top) push(sta[top--] + '0');
  }
  il void write(char *s) { while (*s) push(*s++); }
  il void write(const char *s) { while (*s) push(*s++); }
  il void write(char c) { push(c); }
  il void write(str s) { for (int c : s) push(c); }
  template<typename T, typename... Args> il void write(T x, Args... args) { write(x), write(args...); }
} io;

/*============================DEBUG_AREA============================*/

namespace DDDEBUG {

using std::cerr;
std::ostream &operator<<(std::ostream &os, i128 x) {
  str s; i64 tmp = x;
  while (x) s += '0' + x % 10, x /= 10;
  std::reverse(all(s));
  if (tmp < 0) s = '-' + s;
  return os << s;
}
template<typename X, typename Y>
std::ostream &operator<<(std::ostream &os, std::pair<X, Y> p) {
  return os << '(' << p.fi << ", " << p.se << ")";
}
#ifndef ONLINE_JUDGE
#define debug(x) \
  cerr << "In Line " << __LINE__ << ": " << #x << " = " << x << std::endl
#define look_time cerr << clock() * 1e3 / CLOCKS_PER_SEC << " ms\n"
#define look_memory cerr << fabs(&med - &mst) / 1024.0 / 1024.0 << " mb\n"
#else
#define debug(...) 42
#define look_time 42
#define look_memory 42
#endif

}  // namespace DDDEBUG

using namespace DDDEBUG;

/*================================END================================*/

/*===============================ALGOS===============================*/

namespace basic_algorithm {
template <typename T> il T abs(T a) { return a >= 0 ? a : -a; }
template <typename T> il void chmin(T &a, T b) { if (a > b) a = b; }
template <typename T> il void chmax(T &a, T b) { if (a < b) a = b; }
}  // namespace basic_algorithm

using namespace basic_algorithm;

/*================================END================================*/

constexpr int N = 2e4 + 5;
constexpr int mod = 1e9 + 7;
constexpr int inf = 0x3f3f3f3f;
constexpr i64 inf64 = 0x3f3f3f3f3f3f3f3fll;

std::mt19937 rng(RANDOM_SEED);

bool mst;

int n, K, head[N], cnt, siz[N];
i64 l, r, f[N][22], ml[22];

struct Edge {
  int v, a, b, nxt;
} e[N << 1];

il void add(int u, int v, int a, int b) {
  e[++cnt] = {v, a, b, head[u]}, head[u] = cnt;
  return ;
}

void dfs(int u, int fa, i64 x) {
  f[u][0] = siz[u] = 0;
  for (int i = head[u]; i; i = e[i].nxt) {
    int v = e[i].v, a = e[i].a, b = e[i].b;
    if (v == fa) continue;
    dfs(v, u, x);
    int nsiz = std::min(siz[u] + siz[v] + 1, K);
    for (int j = 0; j <= nsiz; ++j) ml[j] = inf64;
    for (int j = 0; j <= siz[u]; ++j) {
      for (int k = 0; k <= siz[v] && k + j <= K; ++k) {
        if (f[u][j] + f[v][k] + a <= x) chmin(ml[j + k + 1], std::max(f[u][j], f[v][k] + a));
        if (f[u][j] + f[v][k] + b <= x) chmin(ml[j + k], std::max(f[u][j], f[v][k] + b));
      }
    }
    for (int j = 0; j <= nsiz; ++j) f[u][j] = ml[j];
    siz[u] = nsiz;
  }
  return ;
}

il bool check(i64 x) {
  dfs(1, 0, x);
  return f[1][K] <= x;
}

il void solve() {
  io.read(n, K);
  for (int i = 1; i <= n; ++i) head[i] = 0;
  cnt = 0, l = r = 0;
  for (int i = 1; i < n; ++i) {
    int u, v, a, b; io.read(u, v, a, b);
    add(u, v, a, b), add(v, u, a, b);
    r += std::max(a, b);
  }
  while (l < r) {
    i64 mid = (l + r) >> 1;
    if (check(mid)) r = mid;
    else l = mid + 1;
  }
  io.write(l, '\n');
  return ;
}

bool med;

signed main() {
  multitask solve();
  Avada_Kedavra;
}

/*
all the things you do
the words you say
it all comes back to you
*/