#include <iostream>
#include <cstdio>
#include <queue>
#include <map>
#include <cstring>
#define ll long long
#define min(a,b) (((a)<(b))?(a):(b))
using namespace std;
const ll N=1e3+3;
ll head[N],nxt[N*2],to[N*2],c[N*2],f[N*2],num=0;
void add(ll x,ll y,ll c1,ll c2) {
	num++;
	to[num]=y;
	c[num]=c1;
	f[num]=c2;
	nxt[num]=head[x];
	head[x]=num;
}
ll disc[N];
const ll e6=1e6;
int main() {
	freopen("pump.in","r",stdin);
	freopen("pump.out","w",stdout);
	ll n,m;
	cin>>n>>m;
	for(ll i=1; i<=m; i++) {
		ll u,v,c1,c2;
		cin>>u>>v>>c1>>c2;
		add(u,v,c1,c2);
		add(v,u,c1,c2);
	}
	ll bc=1e15,bf=0;
	for(int mid=1;mid<=1000;mid++) {
		memset(disc,0x3f,sizeof(disc));
		priority_queue<pair<ll,ll> >q;
		q.push(make_pair(0,1));
		disc[1]=0;
		while(!q.empty()) {
			ll u=q.top().second;
			q.pop();
			for(ll i=head[u]; i; i=nxt[i]) {
				ll v=to[i];
				if(f[i]<mid) continue;
				ll nc=disc[u]+c[i];
				if(nc<disc[v]) {
					disc[v]=nc;
					q.push(make_pair(-nc,v));
				}
			}
		}
		if(disc[n]<1e15) {
			if(bf*disc[n]<mid*bc) {
				bf=mid;
				bc=disc[n];
			}
		}
	}
	cout<<bf*e6/bc;
	return 0;
}