#include <bits/stdc++.h>
using namespace std;
int main(){
int n,m;
cin>>n>>m;
vector<vector<tuple<int,long,long>>>g(n+1);
for(int i=0;i<m;i++){
    int a,b,c,d;
    cin>>a>>b>>c>>d;
    g[a].emplace_back(b,c,d);
    g[b].emplace_back(a,c,d);
}
auto w=[](long t,long d){
    int l=sqrt(d)-t-10;
    l=max(l,0);
    int m=l;
    for(int i=l;i<20+l;i++)
    if(i+d/(t+i+1)<m+d/(t+m+1))
    m=i;
    return m;
};
priority_queue<pair<long,int>,vector<pair<long,int>>,greater<>>q;
vector<long>D(n+1,1e18);
q.emplace(D[1]=0,1);
while(!q.empty()){
    auto[t,u]=q.top();
    q.pop();
    if(u==n)break;
    if(t>D[u])continue;
    for(auto[v,c,d]:g[u]){
        auto T=t+w(t,d);
        auto x=T+c+d/(T+1);
        if(D[v]>x)q.emplace(D[v]=x,v);
    }
}
cout<<(D[n]<1e18?D[n]:-1)<<endl;
}

//#define MULTICASES
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,a,b) for(i=(a);i<=(b);++i)
#define per(i,a,b) for(i=(a);i>=(b);--i)
#define REP(i,a,b) for(i=(a);i< (b);++i)
#define PER(i,a,b) for(i=(a);i> (b);--i)
#define ERR(...) fprintf(stderr,__VA_ARGS__)
inline void ac();
int main(){
#ifdef MULTICASES
	int t;scanf("%d",&t);while(t--)ac();
#else
	ac();
#endif
	return 0;
}
const int MAXN=200005;
int d,Ans;
vector<int>E[MAXN];
inline int dfs(const int &v=1,const int &f=0){
	int a=-1,b=0,t,u;
	vector<int>::iterator e,ee;
	for(e=E[v].begin(),ee=E[v].end();e!=ee;++e)if((u=*e)!=f){
		t=dfs(u,v);
		if(t<0){if(t<b)b=t;}
		else   {if(t>a)a=t;}
	}
	//ERR("v=%d a=%d b=%d\n",v,a,b);
	//if(a>-b){ERR("I. %d\n",a-1);}
	//else{if(b-1<-d){ERR("II. %d (Ans=%d)\n",d,Ans+1);}else{ERR("III. %d\n",b-1);}}
	if(a>-b)return a-1;
	else{if((--b)<-d){++Ans;return d;}else return b;}
}
inline void ac(){
	int n,k,i,v,u,l,r;
	scanf("%d%d",&n,&k);
	rep(i,2,n){
		scanf("%d%d",&v,&u);
		E[v].push_back(u);
		E[u].push_back(v);
	}
	i=n-1;l=1;r=n-2;
	while(l<=r){
		d=(l+r)>>1;Ans=0;
		if(dfs()<0)++Ans;
		//ERR("\nd=%d Ans=%d\n\n\n\n",d,Ans);
		if(Ans>k)l=d+1;
		else r=(i=d)-1;
	}
	printf("%d\n",i);
}
/*
0. int overflow, array bounds
1. special cases (n=1? n=0?)
2. do smth instead of nothing and stay organized
3. WRITE STUFF DOWN
4. DON'T GET STUCK ON ONE APPROACH
5. STAY CALM AND DON'T GET EXPLODED
*/
