#include <iostream>
#include <iomanip>
#include <vector>
#include <cmath>
#include <algorithm>
#include <set>
#include <queue>
#include <map>
#include <stack>
#include <bitset>
#include <string>
#include <cstring>
#include <iterator>
#include <random>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef long double ld;
const ll dim = 3*1e5+7;
//const ll mod = 1e9 + 7;
const ld inf = 1e18+3;
#define endl "\n"
#define fi first
#define pb push_back
#define se second
#define vll vector<ll>
ll n, m;
vector<pll> a[dim];
map<ll, vector<pair<pll, ll>>> g[dim];
struct edge{
ll u, v, c, p;
};
edge ed[dim];
map<ll, ll> col[dim];
ll dey(ll st, vector<map<ll, ll>> &dst){
dst[st][0]=0;
set<pair<ll, pll>> q;
q.insert({0, {st, 0}});
while(q.size()>0) {
ll v = (*q.begin()).se.fi;
ll tp = (*q.begin()).se.se;
// cout<<v<<" "<<tp<<" "<<dst[v][tp]<<endl;
q.erase(q.begin());
for (auto x: g[v][tp]) {
ll to1 = x.fi.fi;
ll to2 = x.fi.se;
if (dst[to1][to2] > dst[v][tp] + x.se) {
q.erase({dst[to1][to2], {to1, to2}});
dst[to1][to2] = dst[v][tp] + x.se;
q.insert({dst[to1][to2], {to1, to2}});
}
}
}
return dst[n][0];
}
int main() {
ll t, u0, v0;
cin>>n>>m;
for(int i=1; i<=m; i++){
cin>>ed[i].u>>ed[i].v>>ed[i].c>>ed[i].p;
a[ed[i].u].pb({ed[i].v, i});
a[ed[i].v].pb({ed[i].u, i});
}
vector<map<ll, ll>> dst(n+5);
for(int i=1; i<=n; i++){
map<ll, ll> mp;
dst[i][0]=inf;
ll mn=inf;
for(auto x: a[i]){
ll id=x.se;
ll c=ed[id].c;
dst[i][c]=inf;
mp[c]+=ed[id].p;
}
//if(i==1)cout<<
for(auto x:a[i]){
g[i][0].pb({{x.fi, ed[x.se].c}, 0});// фарбуємо наше ребро
g[x.fi][0].pb({ {i, ed[x.se].c}, mp[ed[x.se].c]-ed[x.se].p});// не фарбуємо наше ребро
g[i][0].pb({ {x.fi, 0}, mp[ed[x.se].c]-ed[x.se].p});// не фарбуємо наше ребро
g[x.fi][ed[x.se].c].pb({{x.fi, 0}, ed[x.se].p});
g[x.fi][0].pb({{x.fi, ed[x.se].c}, ed[x.se].p});
//g[i][ed[x.se].c].pb({{i, 0}, ed[x.se].p});
}
}
ll ans=dey(1, dst);
if(ans==inf){
cout<<-1<<endl;
}
else{
cout<<ans<<endl;
}
return 0;
}
