#include<bits/stdc++.h>
#define poly vector<int>
#define IOS ios::sync_with_stdio(false)
#define ll long long
#define mp make_pair
#define mt make_tuple
#define pa pair < int,int >
#define fi first
#define se second
#define inf 1e18
#define mod 998244353
#define sz(x) ((int)((x).size()))
#define int ll
#define N 500005
using namespace std;
int n,m;
struct node
{
    int t,c,w;
};
int dis[N];
vector<node>E[N];
vector<pa>G[N];
map<int,int>val[N],Mp[N];
void BellaKira()
{
    cin>>n>>m;
    for (int i=1;i<=m;i++)
    {
        int x,y,c,p;
        cin>>x>>y>>c>>p;
        E[x].push_back((node){y,c,p});
        E[y].push_back((node){x,c,p});
        val[x][c]+=p;
        val[y][c]+=p;
    }
    int nn=n;
    for (int i=1;i<=n;i++)
        for (auto u:E[i])
        {
            G[i].push_back(mp(u.t,min(u.w,val[i][u.c]-u.w)));
            if (!Mp[u.t].count(u.c))
            {
                Mp[u.t][u.c]=++nn;
            }
            if (!Mp[i].count(u.c))
            {
                Mp[i][u.c]=++nn;
            }
            G[Mp[i][u.c]].push_back(mp(u.t,min(u.w,val[i][u.c]-u.w)));
            G[i].push_back(mp(Mp[u.t][u.c],0));
        }
    priority_queue<pa>q;
    for (int i=1;i<=nn;i++)
        dis[i]=inf;
    dis[1]=0;
    q.push(mp(0,1));
    while (!q.empty())
    {
        int u=q.top().se;
        int w=-q.top().fi;q.pop();
        if (w!=dis[u]) continue;
        for (auto [v,va]:G[u])
            if (dis[v]>dis[u]+va)
            {
                dis[v]=dis[u]+va;
                q.push(mp(-dis[v],v));
            }
    }
    if (dis[n]==inf) cout<<"-1\n";
    else cout<<dis[n]<<'\n';




}
signed main()
{
    IOS;
    cin.tie(0);
    int T=1;
    while (T--)
    {
        BellaKira();
    }
}