#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define for1(i,j,k) for(int i=(j);i<=(k);i++)
#define for2(i,j,k) for(int i=j;i>=k;i--)
#define for3(i,j,k,l) for(int i=j;i<=k;i+=l)
#define bit(n,i) ((n>>i)&1)
#define all(x) x.begin(),x.end()
//#pragma GCC optimize("O2,unroll-loops")
//#pragma GCC target("avx,avx2,bmi,bmi2,sse,sse2,sse3,ssse3,sse4,popcnt")
#define int long long
typedef long long ll;
typedef pair<int,int> pii;
typedef double ld;
typedef pair<ld,ld> pdd;
typedef pair<ll,ll> pll;
typedef vector<pii> vii;
typedef vector<int> vi;
const ll maxn=2e5+5;
const ll offset=1e18;
const ll block_sz=317;
const ll inf=1e18;
const ll mod=1e9+7;
int n,m;
struct Edge
{
int v,c,p;
};
vector<Edge> adj[maxn];
priority_queue<pii,vii,greater<pii>> pq;
int sum[maxn],mn[maxn],dp[maxn];
void sol()
{
cin >> n>>m;
for1(i,1,m)
{
int u,v,c,p;cin >> u>> v>>c>>p;
adj[u].pb({v,c,p});
adj[v].pb({u,c,p});
}
for1(i,1,n) dp[i]=inf;
pq.push({0,1});
dp[1]=0;
while (!pq.empty())
{
int x=pq.top().fi;
int u=pq.top().se;
pq.pop();
if (dp[u]!=x) continue;
for(Edge x:adj[u])
{
int v=x.v;
int c=x.c;
int p=x.p;
sum[c]=0;
mn[c]=inf;
}
for(Edge x:adj[u])
{
int v=x.v;
int c=x.c;
int p=x.p;
sum[c]+=p;
mn[c]=min(mn[c],dp[v]);//mn[c] la min dp[v1]
}
for(Edge x:adj[u])
{
int v=x.v;
int c=x.c;
int p=x.p;
if (dp[v]>dp[u]+min(p,sum[c]-p))
{
dp[v]=dp[u]+min(p,sum[c]-p);
pq.push({dp[v],v});
}
if (dp[v]>mn[c]+sum[c]-p)
{
dp[v]=mn[c]+sum[c]-p;
pq.push({dp[v],v});
}
}
}
if (dp[n]>=inf) cout <<"-1";
else cout << dp[n];
}
int32_t main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t=1;//cin >> t;
while (t--)
{
sol();
}
}
/*
3 5 2 4 1
*/
