#include <iostream>
#include <assert.h>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#define forn(i,n) for(int i=0;i<(int)n;++i)
#define fort(i,n) for(int i=0;i<=(int)n;++i)
#define fori(i,a,n) for(int i=a;i<(int)n;++i)
#define forit(i,a,n) for(int i=a;i<=(int)n;++i)
#define DBG(a) cerr<<#a<<" = "<<(a)<<endl
#define DBGA(a) cerr<<#a<<" = "<<(a)<<", ";
#define DBG2(a,b) do{DBGA(a)DBG(b);}while(0)
#define DBG3(a,b,c) do{DBGA(a)DBGA(b)DBG(c);}while(0)
#define DBG4(a,b,c,d) do{DBGA(a)DBGA(b)DBGA(c)DBG(d);}while(0)
#define ALL(v) v.begin(),v.end()
#define SZ(v) (int)v.size()
using namespace std;
template<typename T>
ostream &operator<<(ostream &os, vector<T> v){
os<<"[";
forn(i,SZ(v)){
if(i) os<<", ";
os<<v[i];
}
os<<"]";
return os;
}
template<typename T>
using PQ = priority_queue<T>;
typedef long long ll;
const ll INF = 1000000000000000000;
struct Edge{
int v, p;
};
struct State{
int u, c; // color que tiene que aprovechar
ll d;
bool operator<(const State &o)const{
return d>o.d;
}
};
void solve(){
int n, m;
cin>>n>>m;
map<int,vector<Edge>> g[n];
forn(i,m){
int u, v, c, p;
cin>>u>>v>>c>>p;
--u,--v;
g[u][c].push_back({v,p});
g[v][c].push_back({u,p});
}
map<int,ll> dist[n];
PQ<State> dij;
dist[0][0] = 0;
dij.push({0,0,0});
while(SZ(dij)){
int u=dij.top().u, c=dij.top().c;
ll d=dij.top().d;
dij.pop();
if(dist[u][c] != d) continue;
//~ DBG3(u,c,d);
if(!c){ // no tiene un color definido para aprovechar
for(const auto &color: g[u]){ // por color
if(!dist[u].count(color.first) || d < dist[u][color.first]){
dist[u][color.first] = d;
dij.push({u,color.first,d});
}
int x = (SZ(color.second) > 1);
for(auto [v,p]: color.second){ // prueba lo siguiente sin problema
ll nd = d + p * x; // solo suma si hay más de uno
if(!dist[v].count(0) || nd < dist[v][0]){
dist[v][0] = nd;
dij.push({v,0,nd});
}
nd = d; // no aumenta con la promesa de que lo va a usar despues
if(!dist[v].count(color.first) || nd < dist[v][color.first]){
dist[v][color.first] = nd;
dij.push({v,color.first,nd});
}
}
}
} else{ // tiene que aprovechar el color sí o sí
ll sum = 0;
for(auto [v,p]: g[u][c]){
sum += p;
}
for(auto [v,p]: g[u][c]){
ll nd = d + sum - p; // cambio el color de todo menos del que voy a atravesar
if(!dist[v].count(0) || nd < dist[v][0]){
dist[v][0] = nd;
dij.push({v,0,nd});
}
}
}
}
ll ans = -1;
if(dist[n-1].count(0)) ans = dist[n-1][0];
cout<<ans<<"\n";
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
#ifdef LOCAL
freopen("D.in", "r", stdin);
int tcs;
cin>>tcs;
while(tcs--)
#endif
solve();
return 0;
}
