#include<bits/stdc++.h>
using namespace std;
using I=int;
using Lli=long long int;
const I N=100000;
const Lli MAX=1e18;
map<pair<I,I>,map<pair<I,I>,Lli>>adjs;
map<I,Lli>tots[N];
priority_queue<tuple<Lli,pair<I,I>,I,Lli>>ques;
map<pair<I,I>,Lli>diss;
void add(Lli dis,I a,I c,I p,Lli pre){
if(!diss.count({a,c}))diss[{a,c}]=MAX;
if(dis>=diss[{a,c}])return;
ques.push({-(diss[{a,c}]=dis),{a,c},p,pre});
}
I main(){
cin.tie(0)->sync_with_stdio(0);
I n,m;cin>>n>>m;
for(I i=0;i<m;i++){
I a,b,c,p;cin>>a>>b>>c>>p,a--,b--,c--;
adjs[{a,c}][{b,c}]=adjs[{b,c}][{a,c}]=p;
adjs[{a,m}][{b,c}]=adjs[{b,m}][{a,c}]=p;
tots[a][c]+=p,tots[b][c]+=p;
}
add(0,0,m,-1,0);
while(ques.size()){
auto[dis,stt1,par,pre]=ques.top();ques.pop();
if((dis=-dis)!=diss[stt1])continue;
for(auto[stt2,p]:adjs[stt1]){
auto[a,c1]=stt1;auto[b,c2]=stt2;
if(b==par)continue;
p=min(p,tots[a][c2]-p-(c1==c2)*pre);
add(dis+p,b,c2,a,p),add(dis+p,b,m,a,p);
}
}
printf("%lli\n",diss.count({n-1,m})?diss[{n-1,m}]:-1);
}
