#include<bits/stdc++.h>

using namespace std;
typedef long long ll;

#define rep(i,n) for (long long i = 0; i < (n); ++i)
#define INF LONG_MAX/3
//#define DIV 1000000007
//#define DIV 998244353

template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};

//pos, C, D;
vector<tuple<ll, ll, ll> > to[100005];

ll cal(double c, double d, double curtime) {
	double s = 0;
	double e = 1000000000;

	while(s + 5 < e) {
		double diff = e - s;
		double p0 = s + diff/3;
		double p1 = s + 2*(diff/3);

		double cost0 = p0 + c + (d/(curtime + p0 + 1));
		double cost1 = p1 + c + (d/(curtime + p1 + 1));

		if(cost0 < cost1) {
			e = p1;
		} else {
			s = p0;
		}
	}

	ll ret = INF;
	for(ll x = max(0LL, (ll)s - 10); x <= s + 20; x++) {
		ll cost0 = x + c + (d/(curtime + x + 1));
		chmin(ret, cost0);
	}
	return ret;
}

int main(){
	ll N, M;
	cin >> N >> M;

	rep(i, M) {
		ll a, b, c, d;
		cin >> a >> b >> c >> d;
		a--;b--;
		to[a].push_back({b, c, d});
		to[b].push_back({a, c, d});
	}


	priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<pair<ll, ll> > >Q;
	Q.push(make_pair(0, 0));

	vector<ll> dis(N, -1);

	while(!Q.empty()) {
		ll cost = Q.top().first;
		ll pos = Q.top().second;
		Q.pop();
		if(dis[pos] != -1) continue;
		dis[pos] = cost;

		for(auto item: to[pos]) {
			ll next, c, d;
			tie(next, c, d) = item;
			ll minicost = cal(c, d, cost);
			//cout << "pos = " << pos << " next = " << next << " cost = " << cost << " mini = " << minicost << endl;
			Q.push({cost + minicost, next});
		}
	}

	cout << dis[N-1] << endl;
}

#include <algorithm>
#include <bitset>
#include <cmath>
#include <complex>
#include <cstdio>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <sys/types.h>
#include <unistd.h>
#include <vector>

#pragma region macros
#define _overload(_1, _2, _3, name, ...) name
#define _rep(i, n) _range(i, 0, n)
#define _range(i, a, b) for (int i = int(a); i < int(b); ++i)
#define rep(...) _overload(__VA_ARGS__, _range, _rep, )(__VA_ARGS__)
#define _rrep(i, n) _rrange(i, n, 0)
#define _rrange(i, a, b) for (int i = int(a) - 1; i >= int(b); --i)
#define rrep(...) _overload(__VA_ARGS__, _rrange, _rrep, )(__VA_ARGS__)
#pragma endregion macros

using namespace std;

template <class T> bool chmax(T &a, const T &b) {
    return (a < b) ? (a = b, 1) : 0;
}
template <class T> bool chmin(T &a, const T &b) {
    return (b < a) ? (a = b, 1) : 0;
}

using ll    = long long;
using R     = long double;
const R EPS = 1e-9L;  // [-1000,1000]->EPS=1e-8 [-10000,10000]->EPS=1e-7
inline int sgn(const R &r) {
    return (r > EPS) - (r < -EPS);
}
inline R sq(R x) {
    return sqrt(max(x, 0.0L));
}

const int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
const int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};

const pid_t pid = getpid();
// Problem Specific Parameter:

int n, k;
const int limit = 200010;
vector<int> graph[limit];
int used[limit];

using state = struct {
    bool covered;
    int dist;
};

state dfs(int v, int p, int thr) {
    vector<int> children;
    for (auto &u: graph[v]) {
        if (u == p) {
            continue;
        }
        children.push_back(u);
    }

    if (children.empty()) {
        return {0, 0};
    }

    int farthest = 0;
    int closest  = 1 << 20;

    for (auto &u: children) {
        const state cur = dfs(u, v, thr);
        if (cur.covered) {
            chmin(closest, cur.dist + 1);
        } else {
            chmax(farthest, cur.dist + 1);
        }
    }

    if (farthest + closest <= thr) {
        return {1, closest};
    } else if (farthest >= thr) {
        used[v] = 1;
        return {1, 0};
    } else {
        return {0, farthest};
    }
}

bool check(int thr) {
    rep(i, n) {
        used[i] = 0;
    }
    const state ret = dfs(0, -1, thr);
    if (ret.covered == 0) {
        used[0] = 1;
    }
    int cnt = 0;
    rep(i, n) {
        cnt += used[i];
    }
    return (cnt <= k);
}

int main(void) {
    cin >> n >> k;

    rep(i, n - 1) {
        int a, b;
        cin >> a >> b;
        a--, b--;
        graph[a].push_back(b);
        graph[b].push_back(a);
    }

    int low = 0, high = n;
    while (high - low > 1) {
        const int mid = (low + high) / 2;
        if (check(mid)) {
            high = mid;
        } else {
            low = mid;
        }
    }

    cout << high << endl;
    return 0;
}