#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define lll __ll128
#define sza(x) ((ll)x.size())
#define all(a) (a).begin(), (a).end()
#define pb push_back
#define pll pair<ll,ll>
#ifdef DEBUG
#include "helper.h"
#else
#define dbg(...)
#endif
#define log(a) 63-__builtin_clzll(a)
const ll INF=1e18;
const ll MOD=1e9+7;
void solve() {
int n,m;
cin>>n>>m;
vector<vector<tuple<int,int,ll>>> edges(n);
vector<map<int,int>> colors(n);
vector<map<int,ll>> dist(n);
vector<map<int,ll>> sums(n);
for(int i=0;i<n;i++){
dist[i][-1]=INF;
}
for(int i=0;i<m;i++){
int a,b,c,d;
cin>>a>>b>>c>>d;
a--,b--;
edges[a].push_back({b,c,d});
edges[b].push_back({a,c,d});
colors[b][c]++;
colors[a][c]++;
sums[a][c]+=d;
sums[b][c]+=d;
dist[a][c]=INF;
dist[b][c]=INF;
}
priority_queue<tuple<ll,int,int> ,vector<tuple<ll,int,int>>,greater<tuple<ll,int,int>>> pq;
pq.push({0,-1,0});
dist[0][-1]=0;
dbg(edges);
while(!pq.empty()){
auto [cost,c,u]=pq.top();
pq.pop();
if(dist[u][c]<cost)continue;
// dbg(u,c);
for(auto [nei,nei_c,nei_cost]:edges[u]){
int color_num=colors[u][nei_c];
assert(color_num!=0);
if(color_num==1){
if(dist[nei][-1]>cost){
dist[nei][-1]=cost;
pq.push({cost,-1,nei});
}
}else if (color_num==2 && nei_c==c){
if(dist[nei][-1]>cost){
dist[nei][-1]=cost;
pq.push({cost,-1,nei});
}
}else{
if(dist[nei][nei_c] > cost+nei_cost){
dist[nei][nei_c]=cost+nei_cost;
pq.push({cost+nei_cost,nei_c,nei});
}
if(dist[nei][-1] > sums[u][nei_c]-nei_cost+cost){
dist[nei][-1]=cost+sums[u][nei_c]-nei_cost+cost;
pq.push({cost+sums[u][nei_c]-nei_cost+cost,nei_c,nei});
}
}
}
}
ll ans=INF;
dbg(dist);
for(auto i:dist[n-1]){
ans=min(ans,i.second);
}
if(ans==INF){
cout<<-1<<endl;
}else{
cout<<ans<<endl;
}
}
int32_t main() {
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
// freopen("boards.in","r",stdin);
// freopen("boards.out","w",stdout);
// cout<<1<<endl;
// dbg(deals);
// ll t;
// cin>>t;
// while(t--)
solve();
}
