#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int nx=1e5+5;
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
struct node
{
ll mn, sm;
vector<pair<ll, ll>> d;
node(): mn(1e18), sm(0){}
};
ll n, m, u, v, c, p, dp[nx];
map<ll, node> mp[nx];
priority_queue<tuple<ll, ll, ll>, vector<tuple<ll, ll, ll>>, greater<tuple<ll, ll, ll>>> pq;
int main()
{
cin.tie(NULL)->sync_with_stdio(false);
cin>>n>>m;
for (int i=1; i<=m; i++) cin>>u>>v>>c>>p, mp[u][c].d.push_back({v, p}), mp[v][c].d.push_back({u, p}), mp[u][c].sm+=p, mp[v][c].sm+=p;
for (int i=2; i<=n; i++) dp[i]=1e18;
pq.push({0, 1, -1});
while (!pq.empty())
{
auto [cw, u, c]=pq.top();
pq.pop();
if (c==-1&&cw>dp[u]) continue;
if (c!=-1&&cw>mp[u][c].mn) continue;
if (c==-1)
{
for (auto [x, d]:mp[u])
{
for (auto [v, w]:d.d)
{
ll cst=min(w, d.sm-w);
if (dp[v]>cw+cst) dp[v]=cw+cst, pq.push({dp[v], v, -1});
if (mp[v][x].mn>cw) mp[v][x].mn=cw, pq.push({mp[v][x].mn, v, x});
}
}
}
else
{
for (auto [v, w]:mp[u][c].d)
{
if (dp[v]>cw+mp[u][c].sm-w) dp[v]=cw+mp[u][c].sm-w, pq.push({dp[v], v, -1});
}
}
}
if (dp[n]==1e18) cout<<-1;
else cout<<dp[n];
}
