#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int MAXN = 4e5;
const int MAXM = 2e6;
const ll INF = 1e18;
struct Edge
{
int u, v, c, p, q;
};
int N, M;
Edge E[MAXN+10];
vector<Edge> adj[MAXN+10], radj[MAXN+10];
map<int, ll> MM[MAXN+10];
vector<int> VV[MAXN+10];
map<int, pii> M2[MAXN+10];
int ncnt=0;
vector<pll> adj2[MAXM+10];
ll dist[MAXM+10];
struct Queue
{
int u; ll w;
bool operator < (const Queue &p) const
{
return w>p.w;
}
};
vector<Edge> V[MAXN+10];
int main()
{
scanf("%d%d", &N, &M);
for(int i=1; i<=M; i++)
{
int u, v, c, p;
scanf("%d%d%d%d", &u, &v, &c, &p);
adj[u].push_back({u, v, c, p, i*2-1});
adj[v].push_back({v, u, c, p, i*2});
radj[u].push_back({v, u, c, p, i*2});
radj[v].push_back({u, v, c, p, i*2-1});
E[i*2-1]={u, v, c, p, i*2-1};
E[i*2]={v, u, c, p, i*2};
MM[u][c]+=p;
MM[v][c]+=p;
}
ncnt=M*2*2;
for(int i=1; i<=N; i++)
{
{
//+in(0)
int v=++ncnt;
M2[i][0].first=v;
for(auto it : radj[i])
{
int u=it.q;
adj2[u].push_back({v, 0});
}
}
{
//-in(0)
int v=++ncnt;
M2[i][0].second=v;
for(auto it : radj[i])
{
int u=it.q+2*M;
adj2[u].push_back({v, 0});
}
}
{
for(auto it : adj[i])
{
V[it.c].push_back(it);
VV[i].push_back(it.c);
}
sort(VV[i].begin(), VV[i].end());
VV[i].erase(unique(VV[i].begin(), VV[i].end()), VV[i].end());
for(auto it : VV[i])
{
int u1=++ncnt, u2=++ncnt;
for(auto jt : V[it])
{
adj2[u1].push_back({jt.q+M*2, jt.p});
adj2[u2].push_back({jt.q, MM[i][it]-jt.p});
}
M2[i][it]={u1, u2};
}
for(auto it : adj[i])
{
V[it.c].clear();
}
}
}
for(int now=1; now<=N; now++)
{
//printf("NOW %d\n", now);
int u1=M2[now][0].first, u2=M2[now][0].second;
//printf("%d %d\n", u1, u2);
for(auto it : VV[now])
{
int v1=M2[now][it].first, v2=M2[now][it].second;
//printf("%d : %d %d\n", it, v1, v2);
adj2[u1].push_back({v1, 0});
adj2[u2].push_back({v1, 0});
adj2[u1].push_back({v2, 0});
adj2[u2].push_back({v2, 0});
}
for(auto nxt : adj[now])
{
int v=M2[nxt.v][nxt.c].second;
adj2[u2].push_back({v, 0});
adj2[u1].push_back({v, 0});
}
}
priority_queue<Queue> PQ;
for(int i=1; i<=ncnt; i++) dist[i]=INF;
PQ.push({M2[1][0].first, 0});
PQ.push({M2[1][0].second, 0});
for(auto it : VV[1])
{
PQ.push({M2[1][it].first, 0});
PQ.push({M2[1][it].second, 0});
}
while(!PQ.empty())
{
Queue now=PQ.top(); PQ.pop();
if(dist[now.u]<=now.w) continue;
//printf("%d %lld\n", now.u, now.w);
dist[now.u]=now.w;
for(auto nxt : adj2[now.u])
{
PQ.push({nxt.first, nxt.second+now.w});
}
}
ll ans=INF;
for(auto nxt : radj[N])
{
//printf("!%d %lld\n", nxt.q, dist[nxt.q]);
//printf("!%d %lld\n", nxt.q+M*2, dist[nxt.q+M*2]);
ans=min(ans, dist[nxt.q]);
ans=min(ans, dist[nxt.q+M*2]);
}
if(ans==INF) ans=-1;
printf("%lld\n", ans);
}
