/*
我是不是要給自己設定一個想題目的時間
hard - 50 分鐘
medium - 30 分鐘
easy - 15 分鐘
*/
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
#define f first
#define s second
#define all(x) x.begin(),x.end()
#define sz(x) (int)(x.size())
#define _ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
void setIO(string s) {
freopen((s + ".in").c_str(), "r", stdin);
freopen((s + ".out").c_str(), "w", stdout);
}
const int mxn=1e5+5;
vector<pair<int,pair<int,int>>> adj[mxn];
map<int,ll> csum[mxn];
ll ans[mxn];
map<int,ll> ans2[mxn];
int main() {_
//setIO("wayne");
// 1. change edge
// 2. change other edges
// 3. change edge and leave next node by edge with same color
int n,m;
cin>>n>>m;
for(int i=0;i<m;i++){
int a,b,c,w;
cin>>a>>b>>c>>w;
adj[a].push_back({b,{c,w}});
adj[b].push_back({a,{c,w}});
csum[a][c]+=w;
csum[b][c]+=w;
}
//{-cost,node,color(if case3)}
priority_queue<tuple<ll,int,int>> pq;
pq.push({0,1,0});
for(int i=1;i<=n;i++) ans[i]=(ll)(1e18);
ans[1]=0;
while(!pq.empty()){
ll val;
int v,c;
tie(val,v,c)=pq.top();
val*=-1;
pq.pop();
if(c){
//if(ans2[v][c]!=val) continue;
for(auto u:adj[v]){
if(u.s.f!=c) continue;
ll res=val+csum[v][c]-u.s.s;
if(res<ans[u.f]){
ans[u.f]=res;
pq.push({-1*ans[u.f],u.f,0});
}
}
}
else{
//if(ans[v]!=val) continue;
for(auto u:adj[v]){
ll val1=val+u.s.s;
if(val1<ans[u.f]){
ans[u.f]=val1;
pq.push({-1*ans[u.f],u.f,0});
}
ll val2=val+csum[v][u.s.f]-u.s.s;
if(val2<ans[u.f]){
ans[u.f]=val2;
pq.push({-1*ans[u.f],u.f,0});
}
ll val3=val;
if(ans2[u.f].count(u.s.f)==0 or val3<ans2[u.f][u.s.f]){
ans2[u.f][u.s.f]=val3;
pq.push({-1*ans2[u.f][u.s.f],u.f,u.s.f});
}
}
}
}
if(ans[n]==(ll)1e18){
cout<<-1;
}
else{
cout<<ans[n];
}
return 0;
}
//maybe its multiset not set
