#include<bits/stdc++.h>
#define newl '\n'
const int N = 1e5 + 10;
const int V = 1e7 + 10;
const long long INF = 1e18;
const long long M = 1e9 + 7;
struct Data{
long long v,c,w;
bool operator > (const Data &other) const {
return (w > other.w);
}
// bool operator < (const Data &other) const {
// return (w < other.w);
// }
};
struct DP{
long long v,c;
bool operator < (const DP &other) const {
return (v < other.v || (v == other.v && c < other.c));
}
};
std::map<int,std::vector<std::pair<int,int>>> adj[N + 1];
std::map<DP,long long> f;
std::map<std::pair<int,int>,long long> s;
int n,m;
void readData(){
std::cin >> n >> m;
for(int i = 1;i <= m;++i){
int u,v,c,w;
std::cin >> u >> v >> c >> w;
adj[u][c].emplace_back(v,w);
adj[v][c].emplace_back(u,w);
}
}
void precompute(){
for(int i = 1;i <= n;++i){
for(const auto &t : adj[i]){
for(const auto &p : t.second){
s[{i,t.first}] += p.second;
}
}
}
}
long long solve(){
std::priority_queue<Data,std::vector<Data>,std::greater<Data>> pq;
pq.push({1,-1,0});
f[{1,-1}] = 0;
while(!pq.empty()){
Data t = pq.top();
DP d = {t.v,t.c};
pq.pop();
if(t.w > f[d]){
continue;
}
// if(t.v == 10){
// std::cerr << t.w << newl;
// std::cerr << "STOP\n";
// }
// if(t.v == 8){
// std::cerr << "STOP";
// }
// assert((f.find({n,-1}) == f.end() || f[{n,-1}] != 0));
if(t.c == -1){
for(const auto &l : adj[t.v]){
for(const auto &nxt : l.second){
DP nD = {nxt.first,-1};
long long nW = t.w + std::min((long long)nxt.second,s[{t.v,l.first}] - nxt.second);
if(f.find(nD) == f.end() || nW < f[nD]){
f[nD] = nW;
pq.push({nD.v,nD.c,nW});
}
nD = {nxt.first,l.first};
nW = t.w;
if(f.find(nD) == f.end() || nW < f[nD]){
f[nD] = nW;
pq.push({nD.v,nD.c,nW});
}
}
}
}else{
for(const auto &nxt : adj[t.v][t.c]){
DP nD = {nxt.first,-1};
long long nW = t.w + s[{t.v,t.c}] - nxt.second;
if(f.find(nD) == f.end() || nW < f[nD]){
f[nD] = nW;
pq.push({nD.v,nD.c,nW});
}
}
}
}
long long ans = INF;
DP d = {n,-1};
DP d1 = {n,-2};
if(f.find(d) != f.end()){
ans = std::min(ans,f[d]);
}
if(f.find(d1) != f.end()){
ans = std::min(ans,f[d1]);
}
return (ans == INF ? -1 : ans);
}
int main(){
std::ios_base::sync_with_stdio(false);
std::cin.tie(nullptr);std::cout.tie(nullptr);
readData();
precompute();
std::cout << solve();
return 0;
}
