#include <bits/stdc++.h>
#define MAX 101000
typedef std::pair<long long,long long> pii;
typedef std::pair<long long,pii> pip;
std::vector<pip> con[MAX];
std::unordered_map<long long,long long> custao[MAX];
std::map<long long,long long> mamg[MAX];
int main()
{
int N,M;
std::cin>>N>>M;
for(int i=0;i!=M;++i){
long long a,b,c,d;
std::cin>>a>>b>>c>>d;--a;--b;
custao[a][c]+=d;
custao[b][c]+=d;
con[a].push_back({b,{c,d}});
con[b].push_back({a,{c,d}});
}
std::priority_queue<pii,std::vector<pii>,std::greater<pii>> queue;
queue.push({0,0});
bool visitou[N]={};
long long valores[N]={};
long long custo=0;
while(queue.size()){
auto _ = queue.top();
queue.pop();
if(visitou[_.second])continue;
visitou[_.second]=true;
valores[_.second]=_.first;
for(auto&x:con[_.second]){
if(mamg[x.first].find(x.second.first)==mamg[x.first].end())
mamg[x.first][x.second.first]=_.first;
long long ajuda=_.first;
auto it = mamg[_.second].find(x.second.first);
if(it!=mamg[_.second].end())ajuda=it->second;
queue.push({std::min(ajuda+custao[_.second][x.second.first]-x.second.second,_.first+x.second.second),x.first});
}
}
if(!visitou[N-1]){
printf("-1\n");return 0;
}
std::cout<<valores[N-1]<<"\n";
}
